첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.
첫째 줄에는 (구역의 개수)/2 값 N과 특수 소대원의 수 W가 주어진다. (1 ≤ N ≤ 10000, 1 ≤ W ≤ 10000).
둘째 줄에는 1~N번째 구역에 배치된 적의 수가 주어지고, 셋째 줄에는 N+1 ~ 2N번째 구역에 배치된 적의 수가 공백으로 구분되어 주어진다. (1 ≤ 각 구역에 배치된 최대 적의 수 ≤ 10000) 단, 한 구역에서 특수 소대원의 수보다 많은 적이 배치된 구역은 존재하지 않는다. (따라서, 각 구역에 배치된 최대 적의 수 ≤ W)
출력
각 테스트케이스에 대해서 한 줄에 하나씩 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 출력하시오.
드디어 도전한 킹격자 갓라기 문제... 충분히 대비했다고 생각했어도 틀리는 건 어쩔 수 없었고, 테스트케이스의 도움을 받아 탈출할 수 있었다. 감사합니다 수많은 선배님들...!!
핵심은 DP를 어떻게 해결할 것이냐이다. 우선 DP[i][j]를 i번째 행의 j번째 열까지 배치한 최솟값이라고 생각하자. j = 0, 1일 경우 윗열, 아랫열 하나만을 배치한 경우이고, j = 2인 경우 윗열 및 아랫열 모두 배치가 완료된 케이스라고 정의하자.
초기화부터 생각해보면, 1번째와 N번째가 아예 이어지지 않는 경우, 1번째 원소 하나만이 N번째와 이어지는 경우 2가지, 둘 다 이어지는 경우 1가지로 총 4가지이다. 이 4가지 경우 중 전자를 제외한 나머지 경우 인접한 두 적들의 합이 W보다 작거나 같을 때만을 고려하도록 한다.
또한 이 4가지는 초기화할 때, 그리고 마지막에 참조하는 DP값이 각각 다르다. 이를테면 아예 이어지지 않는 경우 DP[0][2] = 1 또는 2가 될 수 있다. 하지만 1번째 원소 하나 이상이 이어진 경우이어진 부분의 반대 열에 대한 초기화가 불가능하다. 이를테면, 0번 열이 이어졌다면 DP[0][1]은 존재할 수 없다. 이미 0번 열이 사용되었으므로 1번 열만 사용된 경우 자체를 고려할 수 없기 때문이다. 또한 마지막에 참조하는 값 역시 사용된 경우를 고려해야 한다. 위 네 가지 경우에 대해 각각 DP[N-1][2], DP[N-1][1]. DP[N-1][0], DP[N-2][2]로 대응된다.
다음은 DP의 업데이트이다.
j = 0, 1인 경우, 만약 같은 열의 이전에 인접한 값과의 합이 W 이하라면 둘을 합치는 경우를 고려할 수 있다. 즉 DP[i-1][1-j] + 1 (반대쪽 열이 사용된 경우)로 업데이트할 수 있다. 혹은 DP[i-1][2] + 1 인 경우(즉 (i, j)하나만을 고려하는 경우) 역시 가능하다.
j = 2인 경우, 기본적으로는 (j = 0, 1인 경우 + 1) 을 고려할 수 있다. 혹은 두 열 모두 이전 행의 값과 합칠 수 있는 경우, DP[i-2][2] + 2 값으로도 업데이트할 수 있다.
마지막으로, N <= 2인 엣지 케이스에는 주의해서 적용되어야 한다. 회전해도 같은 경우 등이 있을 수 있다.
풀이 코드
import sys
input = sys.stdin.readline
MAX = float('inf')
def solve() :
global N, W, enemy_list
N, W = map(int, input().split())
enemy_list = [list(map(int, input().split())) for _ in range(2)]
flg = 0
result = MAX
result = min(result, cal_dp(0))
for i in range(2) :
if N > 1 and enemy_list[i][0] + enemy_list[i][-1] <= W :
result = min(result, cal_dp(i+1))
flg += 1
if N > 2 and flg == 2 :
result = min(result, cal_dp(3))
print(result)
def dp_init(dp, mode = 0) :
if mode not in [1, 3] :
dp[0][1] = 1
if mode not in [2, 3] :
dp[0][0] = 1
if mode == 0 and enemy_list[0][0] + enemy_list[1][0] <= W :
dp[0][2] = 1
else :
dp[0][2] = 2
def dp_result(dp, mode = 0) :
if mode == 0 :
return dp[-1][2]
elif mode in [1, 2] :
return dp[-1][2-mode]
else :
return dp[-2][2]
def cal_dp(mode = 0) :
dp = [[MAX]*3 for _ in range(N)]
dp_init(dp, mode)
for i in range(1, N) :
flg = 0
for j in range(2) :
if enemy_list[j][i-1] + enemy_list[j][i] <= W :
flg += 1
dp[i][j] = min(dp[i][j], dp[i-1][1-j]+1)
dp[i][j] = min(dp[i][j], dp[i-1][2]+1)
dp[i][2] = min(dp[i][2], dp[i][j]+1)
if enemy_list[0][i] + enemy_list[1][i] <= W :
dp[i][2] = min(dp[i][2], dp[i-1][2]+1)
if flg == 2 :
if i > 1 :
dp[i][2] = min(dp[i][2], dp[i-2][2]+2)
elif mode == 0 :
dp[i][2] = min(dp[i][2], 2)
return dp_result(dp, mode)
for _ in range(int(input())) :
solve()
