[Python] boj no. 1006 : 습격자 초라기
Problem
https://www.acmicpc.net/problem/1006
Idea
문제를 보고 1x1 혹은 2x1 크기의 사각형을 사용할 수 있는 타일 문제와 비슷하다고 생각했다. 한 가지 다른 점은 타일의 끝이 이어져 도넛의 형태를 이루고 있다는 점이다.
형태를 생각하기 이전에 도넛 형태가 아닌 끝 부분이 이어져 있지 않은 2xN에서의 타일 채우기라고 생각해보자. i번째 열까지의 타일을 모두 채울 때까지의 특수 소대의 수를 dp[i]라고 하면 dp[i]를 구할 수 있는 케이스는 다음과 같다.
- dp[i-1]와 i번째 윗 타일을 채운 상황에서 i번째 아랫 타일을 채우기
- dp[i-1]와 i번째 아랫 타일을 채운 상황에서 i번째 윗 타일을 채우기
- dp[i-1]에서 i번째 열에서 세로 크기가 2인 타일 채우기
- dp[i-2]에서 i-1번째와 i번째 열에서 가로 크기가 2인 타일 두개 채우기
각 케이스를 그림으로 나타내면 다음과 같다.
이 때, 1번과 2번 케이스는 같은 행의 적 수에 따라 필요한 특수 소대의 수가 달라질 수 있다. i번째 윗 구역까지 특수 소대를 채우는 경우 아래 그림과 같은 두 케이스 중 더 적은 특수 소대가 필요한 케이스를 선택해야 한다. 따라서 윗 구역만 커버하는 경우와 아랫 구역만 커버하는 또한 dp로 구할 필요가 있다.
직사각형 형태의 타일 구하기는 위와 같은 기준을 통해 하지만, 이러한 형태에서는 양끝의 구역을 같은 특수 소대가 커버하는 케이스를 고려할 수 없다는 문제점이 있다. 하지만 이는 역으로 말하면 양끝 구역을 같은 특수 소대가 커버하는 상황을 의도하여 만든다면 직사각형 형태의 타일 구하기를 적용하여도 문제가 없게 된다.
양끝의 타일이 연결되는 상황은 다음과 같다.
- 위쪽 양끝 구역의 합이 W보다 작거나 같은 경우 => N번째 아래쪽 구역을 채우는 경우를 구한다(N번째 위쪽 구역은 이미 0번째 위쪽 구역과 함께 커버되고 있으므로)
- 아래쪽 양끝 구역의 합이 W보다 작거나 같은 경우 => N번째 위쪽 구역을 채우는 경우를 구한다(N번째 아래쪽 구역은 이미 0번째 아래쪽 구역과 함께 커버되고 있으므로)
- 1번과 2번 케이스가 함께 나타나는 경우 => dp[N-1]를 구한다
또한 해당 케이스에 포함되는 각 양끝 타일의 크기를 10000으로 설정하여 지정된 구역 이외의 다른 구역과 소대를 공유하는 상황을 없게 만든다.
가능한 모든 케이스를 구한 뒤 가장 적은 특수 소대가 필요한 케이스를 출력한다.
Code
import sys
from copy import deepcopy
input = sys.stdin.readline
def solve(ins, outs, case):
dp = [[0 for _ in range(3)] for _ in range(N+1)] # 꽉 참, inside만 참, outside만 참
for i in range(1, N+1):
dp[i][1], dp[i][2] = dp[i-1][0] + 1, dp[i-1][0] + 1
if i > 1:
if ins[i-1] + ins[i-2] <= W:
dp[i][1] = min(dp[i][1], dp[i-1][2] + 1)
if outs[i-1] + outs[i-2] <= W:
dp[i][2] = min(dp[i][2], dp[i-1][1] + 1)
dp[i][0] = min(dp[i][1], dp[i][2]) + 1
if ins[i-1] + outs[i-1] <= W:
dp[i][0] = min(dp[i][0], dp[i-1][0] + 1)
if i > 1:
if ins[i-1] + ins[i-2] <= W and outs[i-1] + outs[i-2] <= W:
dp[i][0] = min(dp[i][0], dp[i-2][0] + 2)
if case == 0:
return dp[N][0]
elif case == 1:
return dp[N][2]
elif case == 2:
return dp[N][1]
else:
return dp[N-1][0]
T = int(input())
for _ in range(T):
N, W = map(int, input().split())
inside = list(map(int, input().split()))
outside = list(map(int, input().split()))
tempIn = deepcopy(inside)
tempIn[0], tempIn[-1] = 10001, 10001
tempOut = deepcopy(outside)
tempOut[0], tempOut[-1] = 10001, 10001
sol = sys.maxsize
sol = solve(inside, outside, 0)
if N != 1:
if inside[0] + inside[-1] <= W:
sol = min(sol, solve(tempIn, outside, 1))
if outside[0] + outside[-1] <= W:
sol = min(sol, solve(inside, tempOut, 2))
if inside[0] + inside[-1] <= W and outside[0] + outside[-1] <= W:
sol = min(sol, solve(tempIn, tempOut, 3))
print(sol)