[BOJ][KOI] 조약돌 - 25378 (G1)
| 시간 제한 | 메모리 제한 |
|---|---|
| 0.5 초 | 1024 MB |
문제
좌우 한 줄로 있는 N개의 장소 각각에 조약돌이 몇 개씩 놓여 있다.
철수가 할 수 있는 작업의 종류는 아래 두 가지이다.
- 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기
- 한 장소에서 임의의 개수의 조약돌을 가져가기
어떤 장소에 조약돌이 더 이상 없는 경우에도 그 장소는 그대로 남아 있어서, 초기에 인접하지 않았던 두 장소가 인접한 것으로 바뀌지 않는다.
철수는 위의 두 작업 중 하나를 골라서 실행하는 것을 반복하여 모든 조약돌을 가져가려고 한다.
초기에 각 장소에 있는 조약돌들의 개수를 입력받아, 철수가 할 수 있는 최소의 작업 횟수를 계산하는 프로그램을 작성하라.
입력
첫 번째 줄에 장소의 개수 N이 주어진다.
두 번째 줄에 N개의 장소 각각에 있는 조약돌 개수가 왼쪽 장소에 해당하는 것부터 순서대로 공백 하나씩을 사이로 두고 주어진다.
출력
첫 번째 줄에 답을 출력한다.
제한
- 2 ≤ N ≤ 2 500
- 각 장소의 초기 조약돌 개수는 $1$ 이상 $10^8$ 이하이다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | N = 3. |
| 2 | 11 | N ≤ 15. |
| 3 | 19 | N ≤ 300. |
| 4 | 27 | 각 장소의 초기 조약돌 개수가 2 500 이하이다. |
| 5 | 37 | 추가 제약 조건 없음. |
풀이
dynamic programing으로 접근해 보면 조약돌의 오른쪽에서 작업을 시작하여 각 자리마다 그 때의 최소 작업 횟수를 저장하여 memoization할 수 있다.
하지만 단순히 이전까지의 최소 작업 횟수에 현재 자리의 최소 작업을 더한다고 최종적인 최소 작업 횟수가 될 수는 없다. 아래와 같은 예를 보자.
1 3 2
조약돌의 개수가 위와 같이 주어졌을 경우 두 번째 자리까지 최소 횟수는 2이다. 이를 저장하고 다음으로 넘어가서 마지막 자리인 두 개의 조약돌을 빼내는 횟수 1을 단순히 더하면 총 횟수는 3회이다.
하지만 처음부터 1번 작업으로 모두 진행하게 되면 두 번 만에 끝낼 수 있다.
그러므로 단순히 이전까지 최소 횟수에 현재의 최소 횟수를 더하면 안된다.
1번 작업과 2번 작업 간의 작업 횟수 차이를 조금 더 자세히 알아보자.
1번 작업
- r 번째에서 l 번째까지 1번 작업 만으로 모든 자리의 돌의 개수를 0으로 만들 수 있다고 했을 때 작업 횟수는 (l - r) 번이다. (r, r + 1), (r + 1, r + 2), … , (l - 2, l - 1), (l - 1, l) 이와 같은 쌍으로 작업이 진행되므로 (l -r)번 만에 작업을 끝낼 수 있다.
2번 작업
- 이 경우는 해당 범위의 모든 자리의 조약돌을 한 번씩 가져가는 것이므로 범위 내의 자리 개수인 (l - r + 1)과 같은 횟수만큼 작업을 해야 한다.
자리의 범위에 따라 1번 작업으로만 조약돌을 모두 비울 수 있는지 여부가 완전히 달라지기 때문에 이 정보를 사용할 수 있도록 미리 모든 범위에 대해 1번 작업으로만 가능한지 체크해둔다.
위에서 볼 수 있듯이 1번 작업을 최적으로 이용하는 방법을 찾는 것이 이 문제를 푸는데 중요하다는 것을 알 수 있다.
체크하기 가장 쉬운 방법은 매번 인접한 두 조약돌에 대해 1번 작업을 하면서 매번 해당 범위의 조약돌 수의 합을 구해 합이 0이 되었는지 확인해보는 것이지만, 이 경우 $O(n^3)$의 시간복잡도를 가지기 때문에, 이 문제의 모든 서브태스크를 만족하기에 부적합하다.
그래서 아래와 같은 방법을 사용한다.
1
2
3
4
5
6
7
8
9
10
11
check = [[0] * n for _ in range(n)]
for l in range(n - 1):
tmp = nums[l]
for r in range(l + 1, n):
if tmp == nums[r]:
check[l][r] = 1
elif tmp > nums[r]:
break
tmp = abs(tmp - nums[r])
임시 변수(tmp)에 1번 작업을 하고 남은 이전 조약돌의 개수를 저장한다. 임시 변수와 현재 확인하고 있는 자리의 조약돌 개수(nums[r])가 같으면 1번 작업만으로 해당 범위의 자리를 모두 비울 수 있다는 것이므로 체크해준다.
같지 않을 경우 그대로 놔두면 되지만 만약 임시 변수가 현재 조약돌 개수보다 크다면 어떻게 해도 1번 작업만 해서 모두 다 비울 수 없기 때문에 바로 반복문을 종료한다.
위 경우에도 해당되지 않았으면 아직 1번 작업만으로 조약돌을 다 비울 수 있는 가능성이 남아있기 때문에 임시 변수에 임시 변수와 현재 조약돌 개수의 차이로 임시 변수의 값을 바꿔준다. 계속해서 두 값의 차로 값을 바꿔줘야 1번 작업을 하고 남은 이전 조약돌의 개수가 된다.
이제 위에서 체크한 것을 이용하여 최소 시행을 찾아야 한다. 최소 횟수의 후보가 될 수 있는 값은 크게 두 가지가 있다.
$memo[i]$는 $i$까지 작업을 수행했을 때의 최소 횟수, $2\leq i\leq N$ 범위에서 반복하며 확인할 것이므로 $memo[1]=1$로 초기화한다고 하자. 이때 최소 횟수의 후보는 다음과 같다.
$memo[i-1] + 1$
: 이전까지 최소 횟수에 이번 자리의 조약돌을 2번 작업으로 빼내는 횟수(1)를 더한 것
$\min_{1\leq j < i, check[j][i]=1}(memo[j - 1]+i-j)$ $(2\leq i\leq N)$
: 범위가 바뀌었으니 새롭게 1번 작업만으로 비우기가 가능한 범위(체크된 범위)가 있는지 찾아보는 과정이다. $1\leq j < i$를 만족하는 $j$부터 시작해서 새로운 범위의 끝($i$)까지 확인하면서 체크한 범위가 있는지 확인하고 체크된 것이 확인되면 ($check[j][i]=1$) 횟수를 계산한다.
새롭게 찾은 범위가 시작하기 전까지의 최소 횟수($memo[j - 1]$)와 새로운 범위에서 1번 작업을 한 횟수($i-j$)를 더해주면 전체 횟수를 계산할 수 있다.
위 과정으로 구한 두 값 중 작은 것을 해당 위치에서의 최소 횟수로 취하면 된다. 전체 점화식은 다음과 같이 표현할 수 있다.
\[memo[i]=\min\{memo[i-1]+1, \min_{1\leq j < i, check[j][i]=1}(memo[j - 1]+i-j)\}\]1
2
3
4
5
6
7
8
9
10
11
12
13
memo = [0] * (n + 1)
memo[1] = 1
for i in range(2, n + 1):
new_min = float('inf')
for j in range(1, i):
if check[j - 1][i - 1] == 1:
new = memo[j - 1] + i - j
if new_min > new:
new_min = new
memo[i] = min(memo[i - 1] + 1, new_min)
print(memo[-1])
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n = int(input())
nums = list(map(int, input().split()))
check = [[0] * n for _ in range(n)]
memo = [0] * (n + 1)
memo[1] = 1
for l in range(n - 1):
tmp = nums[l]
for r in range(l + 1, n):
if tmp == nums[r]:
check[l][r] = 1
elif tmp > nums[r]:
break
tmp = abs(tmp - nums[r])
for i in range(2, n + 1):
new_min = float('inf')
for j in range(1, i):
if check[j - 1][i - 1] == 1:
new = memo[j - 1] + i - j
if new_min > new:
new_min = new
memo[i] = min(memo[i - 1] + 1, new_min)
print(memo[-1])