티스토리 뷰

1. 물통 (bucket)

크기가 A인 물통과 크기가 B인 물통이 있고, 처음에는 모든 물통이 비어있다. 아래 4가지 동작을 통해 크기가 A인 물통에는 P 만큼, 크기가 B인 물통에는 Q 만큼의 물을 담는 최소 동작 횟수를 구하는 문제다.


1) 크기가 A인 물통을 비우거나 가득 채운다.

2) 크기가 B인 물통을 비우거나 가득 채운다.

3) 크기가 A인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 B인 물통이 가득 차면 옮기는 것을 멈춘다.

4) 크기가 B인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 A인 물통이 가득 차면 옮기는 것을 멈춘다.


크기가 A인 물통에 a만큼의 물이, 크기가 B인 물통에 b만큼의 물이 담겨 있는 상태를 (a, b)라고 나타내자. 초기 상태나 위 4가지 동작 중 하나를 수행한 직후 다음과 같은 조건을 만족한다.


a=0 혹은 a=A 혹은 b=0 혹은 b=B

때문에 가능한 상태의 수는 $O(A+B)$라는 것을 알 수 있고, 이를 이용해 BFS를 통해 최소 동작 횟수를 구할 수 있다.


코드 보기


2. 문명 (civilization)

NxN 크기의 격자판에 초기 K개의 문명 발상지가 있다. 햇수가 지날수록 문명 발상지는 상하좌우로 인접한 칸에 문명을 전파시킨다. 이 때, 모든 문명이 하나로 결합될 때까지 걸리는 최소 햇수를 구하는 문제다.


이 문제를 Parametric search로 접근해서 결정 문제를 Flood-Fill로 해결할 경우 $O(N^2 \lg N)$ 시간복잡도를 가지며, 54점을 받는다.


이 문제를 $O(N^2 \alpha(n))$에 해결하기 위해서는 DSU(Disjoint Set Union, 서로소집합)을 이용하면 된다. 모든 문명이 하나로 결합된다는 것은 연결요소의 개수가 1개라는 것이고, Union-Find를 하면서 연결요소의 개수를 관리할 수 있기 때문에 연결요소의 개수가 1개가 되는 순간을 포착할 수 있다.


코드 보기


3. 요리 강좌 (cook)

N개의 학원 각각에서 M개의 강좌를 개설한다. 각 강좌는 순서대로 수강해야하고, 한 학원에서 연속해서 수강할 수 있는 강좌의 수는 최대 E개다. 그리고 S개 이상의 강좌를 연속해서 수강하면 학원을 옮길 수 있다. 그리고 학원을 옮길 때 비용 T 만큼을 지불해야한다. 마지막으로 각 학원마다 직전 강좌를 특정한 학원에서 수강한 학생을 받지 않는데, 이를 불허용 학원이라 한다. 각 학원마다 각 강좌를 수강하는데 필요한 비용이 주어졌을 때, 한 학생이 모든 강좌를 순서대로 수강하기 위해 필요한 최소 금액을 구하는 문제다.


다음과 같이 DP 배열을 정의한다:

D[i][j] = i번째 강좌까지 수강을 마친 상황이고 마지막으로 강좌를 수강한 학원이 j이며, 이제 막 학원을 옮기려고 할 때 필요한 최소 비용


그러면 점화식은 다음과 같다:

D[i][j] = min(D[k][l] + T + C[j][i] - C[j][k]) (단, S ≤ i-k ≤ E, l ≠ j, l ≠ j의 불허용 학원)

여기서 C[j][i] 는 학원 j에서 첫 강좌부터 i번째 강좌까지 수강했을데 필요한 비용 (즉, 누적합)


DP의 점화식을 보면, i-E이상 i-S이하인 k에 대해 j와 j의 불허용 학원 번호와 다른 모든 l에 대해 D[k][l]-S[j][k]의 최소값을 구하여 T + S[j][i]를 더해주면 D[i][j]가 된다라고 말할 수 있다. [i-E, i-S]라는 구간은 i가 증가할 수록 오른쪽으로 이동하고 l의 조건이 j와 다름,  j의 불허용 학원과 다름, 즉, 2가지라는 것을 고려할 때, N개의 deque와 각 k에 대해 D[k][l]의 최소값 상위 3개를 구해놓음으로써 이 문제를 $O(NM)$ 시간에 DP 배열의 값들을 계산할 수 있다.


DP 배열의 값들을 모두 계산한 뒤에, 답은 $O(NM)$ 시간복잡도로 naive하게 구할 수 있다.


코드 보기


4. 조개 줍기 (shell)

NxN 크기의 격자판에 음이 아닌 정수들이 적혀있다. 그리고 다음과 같이 DP 배열을 정의한다.

D[i][j] = 맨 왼쪽 윗 칸인 시작점에서 i행 j열까지 오른쪽과 아래로만 이동하여 갈 때, 지나간 격자칸에 적힌 수 합의 최대값

그리고 N개의 쿼리가 주어지는데, 각 쿼리는 어떤 특정 칸에 적힌 값을 1증가시키거나 1감소시킨다. 이 때, 각 쿼리를 수행한 후 모든 칸의 DP값의 합을 구하는 문제다.


만약 2행2열에 적힌 값이 변할 때, DP 값이 변하는 칸들은 다음과 같이 "계단" 형식으로 나타낼 수 있다.



즉, 각 행에 대해 DP 값이 변하는 영역은 연속한 구간으로 나타낼 수 있다. 이를 이용하여 DP 값이 변하는 "계단" 모양의 영역을 구한 뒤 각 행에 대해 Fenwick tree를 통해 구간에 특정 값을 더하는 연산을 통하여 DP 값을 관리해줄 수 있다.


총 시간복잡도는 $O(N^2 \lg N)$이다.


코드 보기


저작자 표시
신고
댓글
  • 프로필사진 비밀댓글입니다 2017.07.26 16:37
  • 프로필사진 김민성 고등부 2번 문제에서 Parametric Serarch 를 이용해서 최적화 시키면 만점이 가능한가요? 2017.08.15 21:21 신고
  • 프로필사진 김민성 N제한이 2000이고 K제한이 100000이니 N^2lgN + KlgN정도의 시간 복잡도를 가지는데 충분히 해결 가능하지 않나요?? 2017.08.15 21:38 신고
  • 프로필사진 구사과 대회때 시간 제한이 크지 않았기 때문에 parametric search 포함해서 로그 붙은건 웬만하면 안 나왔습니다.

    parametric search를 어떻게 하느냐도 차이가 클 텐데, 일반적인 flood fill dfs면 입력 크기 감안했을 때 아마 시간 제한이 3초여도 안 나올 겁니다.
    2017.08.16 19:58 신고
댓글쓰기 폼