2021.07.31 ~ 2021.08.06 PS 문제풀이 일지

　여태까지 단순히 solved.ac 레이팅을 올리는 것만을 목적으로 어려운 자료구조 문제만 풀어왔다는 생각이 들어, 최근에는 자료구조 문제는 지양하고, 사고력을 필요로 하는 응용 문제 위주의 문제 풀이를 지향하고자 합니다. 그렇다고 제가 문제 지문만 보고 이게 응용 문제인지 아닌지 판단할 수는 없으므로, 매주 랜덤으로 플래티넘 문제 10문제를 골라 문제풀이를 진행하고 있습니다. 이번주에 선정된 문제는 다음과 같습니다.

　A. BOJ 2102 - 보석 줍기
　B. BOJ 15956 - 숏코딩
　C. BOJ 2598 - 기둥만들기
　D. BOJ 12974 - 시간 여행과 Multiset
　E. BOJ 6000 - 동전 게임
　F. BOJ 12022 - 짝
　G. BOJ 7616 - 교실로 가는 길
　H. BOJ 1146 - 지그재그 서기
　I. BOJ 1258 - 문제 할당
　J. BOJ 1116 - 순열 2

　푼 문제들

　푼 문제들에 대한 풀이는 시간순으로 작성합니다.

　H. BOJ 1146 - 지그재그 서기
　티어: 플래티넘 V

　서로 키가 다른 N명의 학생이 한 줄로 서되, i-1번째 학생이 i-2번째 학생보다 키가 크다면, i번째 학생은 i-1번째 학생보다 키가 작고, i-1번째 학생이 i-2번째 학생보다 키가 작다면, i번째 학생은 i-1번째 학생보다 키가 크도록 하는 경우의 수를 구하는 문제입니다.

　Naive하게 일일히 경우의 수를 하나씩 계산하면 시간복잡도는 O(N!)이고, N이 100 정도이기 때문에, 당연히 시간초과를 받게 됩니다. 따라서 최적화가 필요한데, 가장 쉬운 방법은 dp입니다.

　우선 두 2차원 배열 A와 B가 있다고 합시다. 이때 배열 A[i][j]와 B[i][j]는 둘 다 ‘i번째 학생까지 줄을 세웠을 때, i번째 학생의 키가 j번째로 작은 경우의 수’로 정의하되, 배열 A는 두 번째 학생의 키가 첫 번째 학생보다 큰 경우의 수를, 배열 B는 두 번째 학생의 키가 첫 번째 학생보다 작은 경우의 수를 저장합니다. 그리고 두 dp배열을 다음과 같은 방식으로 채우면 문제를 해결할 수 있습니다.

A[1][1] = B[1][1] = 1
홀수 i에 대하여
- A[i][j] = A[i-1][j] + A[i-1][j+1] + … + A[i-1][i-1]
- B[i][j] = B[i-1][1] + B[i-1][2] + … + B[i-1][j-1]
짝수 i에 대하여
- A[i][j] = A[i-1][1] + A[i-1][2] + … + A[i-1][j-1]
- B[i][j] = B[i-1][j] + B[i-1][j+1] + … + B[i-1][i-1] (홀수의 경우와 반대)
최종 답은 A[n][1] + A[n][2] + … + A[n][n] + B[n][1] + B[n][2] + … + B[n][n]

　학생 1명을 줄 세울때, 첫 번째 학생이 가장 키가 작도록 하는 경우의 수는 당연히 1가지이기 때문에, 첫 번째 조건은 자명합니다. (아직 ‘두 번째 학생’이 정의되지 않았지만, 일단 넘어갑시다.)

　i가 홀수일 경우, 배열 A는 i번째 학생의 키가 i-1번째 학생보다 작은 경우의 수를 계산할 차례입니다. 따라서, 배열 A는 i-1번째 학생의 키가 j번째로 작은 경우의 수부터 i-1번째로 작은(즉, 가장 큰) 경우의 수까지 더해주면 i번째 학생이 i-1번째 학생보다 작고, i번째 학생의 키가 j번째로 작은 모든 경우의 수의 합을 구할 수 있습니다. 배열 B는 반대로 i번째 학생의 키가 i-1번째 학생보다 작은 경우의 수를 계산할 차례이므로, i-1번째 학생의 키가 1번째로 작은 경우의 수부터 j-1번째로 작은 경우의 수까지 모두 더하면 i번째 학생이 i-1번째 학생보다 크고, i번째 학생의 키가 j번째로 작은 모든 경우의 수의 합을 구할 수 있습니다.

　그러나, 이대로 제출하면 틀렸습니다를 받게 됩니다. 이는 N=1인 경우 때문인데, 따로 예외처리를 해주면 O(N^3)의 시간복잡도로 AC를 받을 수 있습니다. (누적 합을 사용하면 O(n^2)에도 가능해보이나, 제한이 널널하여 굳이 하지 않았습니다.)

　J. BOJ 1116 - 순열 2
　티어: 플래티넘 II

　0부터 N-1까지 모든 정수를 포함하는 순열 A에 대하여, 다음과 같은 배열 B를 A의 자식 배열이라고 정의합니다.

B[0] = 0
B[i] = A[B[i-1]]

　길이가 N인 순열 P가 주어졌을 때, P와 차이가 가장 작은(P[i]와 Q[i]의 값이 다른 경우가 최소인) 완벽한 순열 Q를 구하는 문제입니다. 이러한 Q가 여러 개일 경우, 자식 배열이 사전순으로 가장 앞서는 것을 골라야 합니다.

　가장 먼저 해볼만한 관찰은, 순열 P를 그래프 관점으로 보는 것입니다. 예를 들어, P[0]이 4라면, ‘이는 그래프 P의 0번 정점에서 4번 정점으로 가는 간선이 있다’로 해석할 수 있습니다. 이렇게 형성된 그래프 P는 1개 이상의 사이클을 형성합니다. 여기서 추가적으로 해볼 수 있는 관찰은, 서로 다른 사이클에 속하는 순열의 두 원소를 swap하면, 하나의 큰 사이클로 합쳐진다는 것입니다. 이 내용이 이해가 잘 되지 않는다면, 아래 이미지를 참고하면 됩니다.

　이런 식으로 swap을 cycle 개수-1번 하면 차이가 가장 작은 완벽한 순열 Q를 얻을 수 있지만, 자식 배열이 사전순으로 가장 앞서는 것을 골라야 하므로, 추가적인 처리가 더 필요합니다. ‘사전순’의 정의상 작은 숫자가 앞에 등장하는 것이 무조건 이득이므로, 각 사이클별로 가장 작은 숫자를 고른 후 오름차순으로 정렬하여, 배열 Q에 등장하는 순서대로 정렬해 주면 됩니다.

　단, Q[0]을 포함하는 사이클에서 swap하는 경우를 주의해야 합니다. Q[0]를 포함하는 다른 사이클에 Q[0]보다 큰 수가 없는 경우, Q[0]과 swap하는 것은 무조건 손해이므로 해당 사이클의 다음 원소와 swap해야 하며, 그 원소도 마찬가지일 경우 그 다음원소, 그리고 해당 사이클의 모든 원소가 다른 사이클의 가장 작은 숫자보다 작은 경우, 해당 사이클의 마지막 원소와 swap을 해야 합니다.

　D. BOJ 12974 - 시간 여행과 Multiset
　티어: 플래티넘 III

　쿼리 문제입니다. 입력은 다음 세 가지 쿼리로 구성되어 있습니다

특정 시간 t로 가서 multiset에 정수 x 추가
특정 시간 t로 가서 multiset에 정수 x 제거
특정 시간 t에 multiset에 정수가 몇 개 있는지 출력

　추가로, 문제의 description이 다소 애매해서 헷갈리기 쉬운데, 3번 쿼리를 수행하는 시점에, 해당 시점 이후에 진행된 1, 2번 쿼리는 고려하지 않아도 됩니다.

　이 문제는 좌표압축을 수행한 후, 각 노드마다 map을 들고 있는 세그먼트 트리를 구성하면 O(Nlog^2N)에 문제를 해결할 수 있습니다. 이때 map은 각 구간에 어떤 수가 몇 개씩 있는지를 저장합니다.

　I. BOJ 1258 - 문제 할당
　티어: 플래티넘 III

　N명의 학생과 N명의 문제가 있고, 모든 학생이 각 문제를 푸는데 걸리는 시간이 주어지는데, 각 학생이 서로 다른 문제를 1문제씩만 풀 때 문제를 푸는 데 걸리는 시간의 합을 최소화하는 문제입니다.

　하필 이 문제를 읽기 직전에 비슷한 느낌으로 O(N!)을 O(N^3)(내지는 O(N^4))으로 최적화하는 H번을 봐버리는 바람에 한참을 DP가지고 뇌절한 문제입니다. 그런데 정작 풀이는 MCMF였습니다. Source -> 학생 방향과 문제 -> Sink 방향 으로 유량 1, cost 0의 간선을, 학생 -> 문제 방향으로 유량 1과 입력으로 주어진 cost의 간선을 추가하고 MCMF를 돌리면 걸리는 시간의 합을 쉽게 구할 수 있었습니다.