안녕하세요. Softeer 운영 담당자 입니다.

지난 9월 6일에 Softeer 4회 정기 인증평가가 실시되었습니다.

이번 역량 진단에도 많은 분들께서 관심을 가지고 참여하여 주셨습니다.

인증을 받으신 분들께는 축하의 말씀을 전하고, 아깝게 떨어지신 분들께는 안타까운 마음을 전합니다.

금번 평가문제는 연습문제를 통해 확인하실 수 있으며, 문제 해설과 풀이 방법을 공유하오니 역량을 키우시는 데 조금이나마 도움이 되셨으면 좋겠습니다.

향후 정기 인증평가 문제도 연습문제와 문제해설을 업로드 할 계획이니, 많은 관심을 가지고 인증평가에 참여해주시면 감사하겠습니다.

1번 문제

슈퍼컴퓨터 클러스터

풀이 권장 시간: 70분

성능이 가장 낮은 컴퓨터의 성능을 주어진 예산(1≤B≤10¹⁸)으로 최대화한 값을 구해내야 합니다.

각 컴퓨터에 업그레이드를 적용할 수 있는 방법은 1) 하지 않거나, 2) 단 한 번만 d²의 비용을 들여 성능을 d만큼 향상시키는 두 가지 방법밖에 없습니다.

따라서, 성능이 가장 낮은 컴퓨터의 성능을 원하는 수준으로 향상시키기 위한 방법은 오직 한 가지밖에 없습니다.

마찬가지로, 모든 컴퓨터에 각각 상기한 두 가지 방법 중 하나를 적용하여 목표를 달성하는 방법은 유일하게 정해져 있습니다.

[1] 총 비용 계산하기

모든 컴퓨터들 중 가장 낮은 컴퓨터의 성능을 A로 만들고자 한다면, 각 컴퓨터의 성능을 최소 A가 되도록 만드는 데 필요한 비용을 모두 더하면 됩니다.

diff = (A-a[i]>0) ? A-a[i] : 0(여기서 a[i]는 i번째 컴퓨터의 원래 성능입니다.)

diff는 i번째 컴퓨터의 성능을 최소 A가 되도록 만들기 위해 업그레이드를 통해 향상시켜야 하는 수치를 나타냅니다. 그 다음에,

diff²를 계산해서 초깃값을 0으로 정해 놓은 64비트 정수형 변수에 차례대로 더해주면 총 비용을 계산해낼 수 있습니다.

[2] Binary search algorithm

아주 큰 금액의 예산(1≤B≤10¹⁸)이 책정되어 있습니다.

예산을 활용하여 최대한으로 높일 수 있는 컴퓨터의 성능은 2000000000 (이십 억)입니다. N이 1인 경우,

즉 10⁹의 성능을 보유한 컴퓨터 한 대에 10¹⁸의 예산을 모두 쏟아 부으면 10⁹만큼의 성능을 향상시킬 수 있습니다.

2×10⁹이나 되는 큰 숫자부터, 성능이 가장 낮은 컴퓨터의 성능이 1이 될 때까지 가능한 모든 성능에 대해서 [1]의 과정을 반복(시간제한 초과)할 수는 없습니다.

하지만 B만큼의 예산으로 최선의 최저성능이 A 이상이 되도록 만들 수 있다면,

마찬가지로 A-1, A-2, ..., 1 이상이 된다는 사실을 이용하면 성능을 탐색하는 시간을 크게 줄일 수 있습니다.

이진 탐색 알고리즘 (Binary search algorithm) 사용하면, 본 문제를 시간 제한 안에 해결할 수 있습니다.

결국, 결과값으로 출력해야 하는 것은 성능이 가장 낮은 컴퓨터의 성능의 최댓값이기 때문에

B의 예산을 이용하여 A이상으로 만들 수 있는 가장 큰 자연수 A의 값을 알고리즘을 활용해 찾아내면 되는 것입니다.

위에서, 정답으로 가능한 최댓값을 미리 구했었기 때문에,

left = 1과 right = 2000000000의 초기 조건을 가지고 예산 A에 대한 이진 탐색 알고리즘을 수행하면서 [1]의 계산 과정을 반복하면 문제를 해결할 수 있습니다.

[3] 경계 조건

컴퓨터가 아주 많으면서, 대부분의 컴퓨터가 1의 성능을 가지고 있는 경우를 생각해볼 수 있습니다.

이진 탐색 알고리즘을 적용하면, 위의 실행문이 아래와 같이 변형됩니다.

mid = (left+right)/2

diff = (mid-a[i]>0) ? mid-a[i] : 0

초기 조건 상태에서 계산한 mid의 값은 1000000000이기 때문에, 1의 성능을 가지고 있는 모든 컴퓨터에 대해서 999999999²의 비용을 더하게 될 것입니다.

따라서, 주어진 컴퓨터의 개수가 많아질 경우, 64비트 정수형 변수로도 저장할 수 없게 됩니다.

B의 제약조건이 크긴 하지만, 1의 성능을 보유한 컴퓨터 두 대의 성능을 1000000000로 향상시키기에는 충분하지 않습니다.

long과 같은 64비트 정수형 변수에다가 총 비용을 계속해서 더하고, 예산 B의 값과 비교를 통해서 이진 탐색 알고리즘의 다음 단계로 나아가기 위해서는

변수에 저장되어 있는 (현재까지의) 총 비용이 B 보다 커지는 순간 break문등을 활용해서 더 이상 쓸데없는 덧셈이 계속되지 않도록 멈춰주어야 합니다.

2번 문제

통근버스 출발 순서 검증하기

풀이 권장 시간: 70분

주어진 순열이 있을 때, 스택을 사용해서 번호 순서 대로 정렬이 불가능함을 증명할 수 있는 순서쌍 (i, j, k)의 개수를 구하는 문제입니다.

문제에서 주어져 있는 조건은 a_i＜a_j와 a_i＞a_k입니다. (단, i＜j＜k를 만족합니다.)

N-1번째와 N번째 번호를 제외하고, 순서쌍에서 i를 선택할 수 있는 경우의 수는 N-2가지입니다.

다음으로, a_i＜a_j의 조건을 만족하면서 i < j 인 j를 고르고, 마지막으로 a_i＞a_k의 조건을 만족하면서 j < k 인 k를 고를 수 있는 방법의 가짓수를 전부 계산하면

O(N³)의 시간복잡도를 가지고 있는 알고리즘을 구현할 수 있습니다.

그러나, N 의 최댓값은 5000 이기 때문에, 위와 같은 방법으로 풀게 되면 시간 제한 안에 계산을 끝마칠 수 없습니다.

[1] k로 고를 수 있는 경우의 수 미리 계산하기

k를 고르기 위해서는, j＜k≤N 인 자연수 k들 중 a_i＞a_k를 만족하는 경우를 찾아내야 합니다.

이때, a_i로 가능한 값들이 1 이상 N 이하의 자연수로 제한되어 있기 때문에, 1 이상 N 이하의 특정한 자연수보다 작도록 a_k를 j＜k≤N 에서 미리 계산할 수 있는 방법을

구간합 아이디어를 활용해 구현할 수 있습니다.

즉, 임의의 자연수 X(1≤X≤N)에 대하여, arr[X][j]를 j 번째보다 오른쪽에 있는 숫자들 중, x 보다 값이 작은 것들의 개수라고 정의할 수 있습니다.

각각의 x에 대해, j가 N일 때 N번째보다 오른쪽에 있는 숫자는 없으므로, arr[X][N] = 0이고, j 가 N-1일 때는 다음과 같이 계산이 가능합니다.

arr[X][N-1] = (a[N-1]) ? 1 : 0

이어서,

arr[X][j] = arr[X][j+1] + (a[j] < X ? 1 : 0) (여기서 a[j]는 순열의 j 번째 숫자입니다.)

j가 1이 될 때까지 반복하므로, 총 시간복잡도는 O(N²)입니다.

[2] arr를 이용해서 정답 구하기

i < j와 a_i＜a_j를 동시에 만족하는 모든 i 와 j에 대하여, arr[a[i]][j]를 초깃값을 0으로 정해 놓은 64비트 정수형 변수에 모두 더해주면 모든 순서쌍의 개수를 구할 수 있습니다.

결국, 위에서 계산한 방법에 따라서 arr[a[i]][j] 의 값은 j번째보다 오른쪽( j < k )에 있는 숫자들 중 a[i] > a[k] 인 것들의 개수,

즉 j < k 와 a_i＞a_k를 동시에 만족하는 k 의 가짓수이기 때문입니다.