def solve(i):
DP = [[2*N]*(N+1) for i in range(4)]; DP[i][-1] = 0
for n in range(N):
for i in range(4):
DP[0][n] = min(DP[0][n],DP[i][n-1]+int(i&1==0)+int(i&2==0))
if enemy[0][n]+enemy[1][n]<=M:
DP[0][n] = min(DP[0][n],DP[0][n-1]+1)
if enemy[0][n]+enemy[0][n+1]<=M:
DP[1][n] = min(DP[0][n-1]+2,DP[2][n-1]+1)
if enemy[1][n]+enemy[1][n+1]<=M:
DP[2][n] = min(DP[0][n-1]+2,DP[1][n-1]+1)
if enemy[0][n]+enemy[0][n+1]<=M and enemy[1][n]+enemy[1][n+1]<=M:
DP[3][n] = DP[0][n-1]+2
return DP
for _ in range(int(input())):
N,M = map(int,input().split())
enemy = [[*map(int,input().split()),0] for i in range(2)]
result = solve(0)[0][N-1]
if enemy[0][0]+enemy[0][N-1]<=M:
DP = solve(1)
result = min(result,DP[2][N-2]+1,DP[0][N-2]+2)
if enemy[1][0]+enemy[1][N-1]<=M:
DP = solve(2)
result = min(result,DP[1][N-2]+1,DP[0][N-2]+2)
if enemy[0][0]+enemy[0][N-1]<=M and enemy[1][0]+enemy[1][N-1]<=M:
result = min(result,solve(3)[0][N-2]+2)
print(result)다이나믹 프로그래밍 문제이다.
이 문제에 대한 악명이 자자해서 지레 겁먹고 오랫동안 방치했던 문제였는데, 막상 풀어보니 생각보다 간단한 문제였다.
아마 원형이라는 점이 이 문제의 접근난이도를 높이는 요소중 하나일 것이다. 하지만 원형이라는 점을 배제하고 문제를 풀고나면 원형일 때에 대한 예외도 쉽게 해결할 수 있다.
타일채우기 [백준 2718번] 타일 채우기 (Python3) (tistory.com) 나 격자판 채우기 [백준 1648번] 격자판 채우기 (Python3) (tistory.com) 문제에서의 아이디어가 해결에 도움이 되었다.
풀이를 설명하면,
1. DP 배열을 4*(N+1)로 만든다. DP[i][n]에서 i는 n번째 구역까지 채웠을 때 다음 구역도 채워졌는지에 대한 여부를 비트로 나타낸 것이다. 예를들어, n=2=10(2)인 경우 n+1번째 두번째 줄 구역이 채워져있다. (N+1개로 만드는 이유는 초기값을 쉽게 설정하기 위해서이다)
2. 두 개 구역을 커버할 수 있는 경우에는 두 개 구역을 채우는데 1만큼, 그 외에는 구역의 개수만큼을 소모하면서 이전의 모양에서 현재 모양을 만들 수 있는 최솟값을 bottom-up 방식으로 구한다.
3. 원형에서 가장 처음과 가장 끝이 연결되지 않은 경우, 첫째줄이 연결된 경우, 둘째줄이 연결된 경우, 모두 연결된 경우 총 4가지 경우에 대한 최솟값을 구하여 출력한다.
조건이 붙고 원형인 격자판 채우기 문제라고 생각하면 쉽다. 두 개 구역의 합이 M보다 작으면 1*2짜리 블록을, 아니면 1*1짜리 블록을 사용하여 블록의 최소개수로 격자를 채우는 문제이다.
오늘의 교훈) 어려워 보이는 문제도 의외로 쉽게 해결할 수 있지도 모르니 지레 겁먹지 말자.