백준 1006번_습격자 초라기(Python)

문제

초라기는 한국의 비밀국방기지(원타곤)를 습격하라는 임무를 받은 특급요원이다. 원타곤의 건물은 도넛 형태이며, 초라기는 효율적인 타격 포인트를 정하기 위해 구역을 아래와 같이 두 개의 원 모양으로 나누었다. (그림의 숫자는 각 구역의 번호이다.)

초라기는 각각 W명으로 구성된 특수소대를 다수 출동시켜 모든 구역에 침투시킬 예정이며, 각 구역 별로 적이 몇 명씩 배치되어 있는지는 초라기가 모두 알고 있다. 특수소대를 아래 조건에 따라 침투 시킬 수 있다.

1. 한 특수소대는 침투한 구역 외에, 인접한 한 구역 더 침투할 수 있다. (같은 경계를 공유하고 있으면 인접 하다고 한다. 위 그림에서 1구역은 2, 8, 9 구역과 서로 인접한 상태다.) 즉, 한 특수소대는 한 개 혹은 두 개의 구역을 커버할 수 있다.
2. 특수소대끼리는 아군인지 적인지 구분을 못 하기 때문에, 각 구역은 하나의 소대로만 커버해야 한다.
3. 한 특수소대가 커버하는 구역의 적들의 합은 특수소대원 수 W 보다 작거나 같아야 한다.

이때 초라기는 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 알고 싶어 한다.

 

풀이

INF = 10**9

for _ in range(int(input())):
    N, W = map(int, input().split())
    wonTagon = [([0]+list(map(int, input().split()))),([0]+list(map(int, input().split())))]
    DP = [[INF]*3 for i in range(N+1)]
    ans = INF
    if N == 1:
        if wonTagon[1][1]+wonTagon[0][1]<=W:
            print(1)
        else:
            print(2)
    else:
        #case1
        DP[0][0] = 0
        if wonTagon[1][1]+wonTagon[0][1]<=W:
            DP[1][0] = 1
        else:
            DP[1][0] = 2
        DP[1][1] = 1
        DP[1][2] = 1
        
        for i in range(2, N+1):
            #DP[i][0]
            if wonTagon[0][i]+wonTagon[1][i] <= W:
                DP[i][0] = min(DP[i][0], DP[i-1][0]+1)
            else:
                DP[i][0] = min(DP[i][0], DP[i-1][0]+2)
            if wonTagon[0][i-1]+wonTagon[0][i] <= W and wonTagon[1][i-1]+wonTagon[1][i] <= W:
                DP[i][0] = min(DP[i][0], DP[i-2][0]+2)
            elif wonTagon[0][i-1]+wonTagon[0][i] <= W:
                DP[i][0] = min(DP[i][0], DP[i-1][2]+2)
            elif wonTagon[1][i-1]+wonTagon[1][i] <= W:
                DP[i][0] = min(DP[i][0], DP[i-1][1]+2)
            
            #DP[i][1]
            DP[i][1] = min(DP[i][1], DP[i-1][0]+1)
            if wonTagon[0][i-1]+wonTagon[0][i] <= W:
                DP[i][1] = min(DP[i][1], DP[i-1][2]+1)
            
            #DP[i][2]
            DP[i][2] = min(DP[i][2], DP[i-1][0]+1)
            if wonTagon[1][i-1]+wonTagon[1][i] <= W:
                DP[i][2] = min(DP[i][2], DP[i-1][1]+1) 
        ans = min(ans, DP[N][0])
        
        #case 2: inner combine(ㅗ)
        if wonTagon[0][1]+wonTagon[0][N] <= W:
            DP = [[INF]*3 for i in range(N+1)]
            DP[0][0] = INF
            DP[1][0] = 2
            DP[1][1] = min(1, DP[1][1])
            DP[1][2] = INF
            for i in range(2, N+1):
                if i != N:
                    #DP[i][1]
                    if wonTagon[0][i]+wonTagon[1][i] <= W:
                        DP[i][0] = min(DP[i][0], DP[i-1][0]+1)
                    else:
                        DP[i][0] = min(DP[i][0], DP[i-1][0]+2)
                    if wonTagon[0][i-1]+wonTagon[0][i] <= W and wonTagon[1][i-1]+wonTagon[1][i] <= W:
                        DP[i][0] = min(DP[i][0], DP[i-2][0]+2)
                    elif wonTagon[0][i-1]+wonTagon[0][i] <= W:
                        DP[i][0] = min(DP[i][0], DP[i-1][2]+2)
                    elif wonTagon[1][i-1]+wonTagon[1][i] <= W:
                        DP[i][0] = min(DP[i][0], DP[i-1][1]+2)
                    
                    #DP[i][1]
                    DP[i][1] = min(DP[i][1], DP[i-1][0]+1)
                    if wonTagon[0][i-1]+wonTagon[0][i] <= W:
                        DP[i][1] = min(DP[i][1], DP[i-1][2]+1)
                
                #DP[i][2]
                DP[i][2] = min(DP[i][2], DP[i-1][0]+1)
                if wonTagon[1][i-1]+wonTagon[1][i] <= W:
                    DP[i][2] = min(DP[i][2], DP[i-1][1]+1)
            ans = min(ans, DP[N][2])
        #case 3: outer combination(ㅜ)
        if wonTagon[1][1]+wonTagon[1][N] <= W:
            DP = [[INF]*3 for i in range(N+1)]
            DP[0][0] = INF
            DP[1][0] = 2
            DP[1][2] = min(1, DP[1][2])
            DP[1][1] = INF
            for i in range(2, N+1):
                if i != N:
                    #DP[i][1]
                    if wonTagon[0][i]+wonTagon[1][i] <= W:
                        DP[i][0] = min(DP[i][0], DP[i-1][0]+1)
                    else:
                        DP[i][0] = min(DP[i][0], DP[i-1][0]+2)
                    if wonTagon[0][i-1]+wonTagon[0][i] <= W and wonTagon[1][i-1]+wonTagon[1][i] <= W:
                        DP[i][0] = min(DP[i][0], DP[i-2][0]+2)
                    elif wonTagon[0][i-1]+wonTagon[0][i] <= W:
                        DP[i][0] = min(DP[i][0], DP[i-1][2]+2)
                    elif wonTagon[1][i-1]+wonTagon[1][i] <= W:
                        DP[i][0] = min(DP[i][0], DP[i-1][1]+2)
                    
                #DP[i][1]
                DP[i][1] = min(DP[i][1], DP[i-1][0]+1)
                if wonTagon[0][i-1]+wonTagon[0][i] <= W:
                    DP[i][1] = min(DP[i][1], DP[i-1][2]+1)
                
                if i != N:
                    #DP[i][2]
                    DP[i][2] = min(DP[i][2], DP[i-1][0]+1)
                    if wonTagon[1][i-1]+wonTagon[1][i] <= W:
                        DP[i][2] = min(DP[i][2], DP[i-1][1]+1)
            ans = min(ans, DP[N][1])  
        #case 4: both combination(=)
        if wonTagon[0][1]+wonTagon[0][N] <= W and wonTagon[1][1]+wonTagon[1][N] <= W:
            DP = [[INF]*3 for i in range(N+1)]
            DP[0][0] = INF
            DP[1][0] = 2
            DP[1][2] = INF
            DP[1][1] = INF
            for i in range(2, N):
                #DP[i][1]
                if wonTagon[0][i]+wonTagon[1][i] <= W:
                    DP[i][0] = min(DP[i][0], DP[i-1][0]+1)
                else:
                    DP[i][0] = min(DP[i][0], DP[i-1][0]+2)
                if wonTagon[0][i-1]+wonTagon[0][i] <= W and wonTagon[1][i-1]+wonTagon[1][i] <= W:
                    DP[i][0] = min(DP[i][0], DP[i-2][0]+2)
                elif wonTagon[0][i-1]+wonTagon[0][i] <= W:
                    DP[i][0] = min(DP[i][0], DP[i-1][2]+2)
                elif wonTagon[1][i-1]+wonTagon[1][i] <= W:
                    DP[i][0] = min(DP[i][0], DP[i-1][1]+2)
                    
                #DP[i][1]
                DP[i][1] = min(DP[i][1], DP[i-1][0]+1)
                if wonTagon[0][i-1]+wonTagon[0][i] <= W:
                    DP[i][1] = min(DP[i][1], DP[i-1][2]+1)
                else:
                    DP[i][1] = min(DP[i][1], DP[i-1][2]+2)
                
                #DP[i][2]
                DP[i][2] = min(DP[i][2], DP[i-1][0]+1)
                if wonTagon[1][i-1]+wonTagon[1][i] <= W:
                    DP[i][2] = min(DP[i][2], DP[i-1][1]+1)
                else:
                    DP[i][2] = min(DP[i][2], DP[i-1][1]+2) 
            ans = min(ans, DP[N-1][0]) 
        print(ans)

 

해설

2*1 블럭과 1*1 블럭을 배치해서 2*n 길이 막대기를 만드는 것과 같이 다음과 같이 점화식을 만들어 풀 수 있다. 맨 처음 칸부터 차례차례 탐색한다 했을 때, n번째 칸들에서 

 

DP[n][0]: 바깥쪽 칸과 안쪽칸에서 블록이 동시에 끝나는 경우, 즉 n+1번째 칸과 이어진 블록이 없는 경우

DP[n][1]: 안쪽칸만 n+1번째 칸과 이어진 경우

DP[n][2]: 바깥쪽 칸만 n+1번째 칸과 이어진 경우

 

로 정해서 메모리제이션을 하자. 이때 DP[n][0]에 대한 점화식은 다음과 같다.

• DP[n][0] = min(DP[n-1][0]+1 or 2, DP[n-1][1]+2, DP[n-1][2]+2, DP[n-2][0]+2)

이때 'or'은 두 칸의 적의 총합이 W보다 작을 때만 이어붙일 수 있으므로 각 칸의 조건에 맞춰 조건문을 적절히 써줘야 해야 한다는 뜻이다. 

위 점화식을 뜯어서 보면, 우선 DP[n-1][0]+1 or 2는 바로 전칸에서 블록들이 끝난 상태로, 다음과 같은 상황에서 DP[n][0]을 구축하려는 것이다. 아래 그림에서 위를 바깥쪽, 아래를 안쪽으로 본다.

n번째 칸들에서도 위아래 모두 블록이 끝나려면 서로 떨어져 있거나, 가능하다면 위아래로 이어붙이는것이 소대 수를 줄이는데 유리하므로 위아래 적의 합이 W보다 작다면 1을, 아니라면 2를 더한 값이다.

 

그다음 DP[n-1][1]+2는 다음과 같은 경우다.

 

아랫칸만 N-1에서 끝나고, 윗칸은 N번째 칸까지 이어져 있다. 이 경우는 무조건 N-1과 N번째의 윗칸들을 연결할 수 있어야만 계산해야 한다. 

 

DP[N-1][2]+2도 비슷하게 계산된다.

 

그리고 DP[N-2][0]+2는 다음과 같은 경우다.

이 경우에는 위 아래 모두 N과 N-1이 연결이 되어야 한다.

 

 

또한, DP[N][1]에 대한 점화식은 다음과 같다.

• DP[N][1] = min(DP[N-1][0]+1, DP[N-1][2]+1)

여기서 DP[N-1]+1은 다음과 같은 상황을 의미한다.

이미 N-1번째가 다 채워져 있는 상황에 안쪽 칸만 잠입한다.

 

DP[N-1][2]+1는 다음과 같은 상황을 의미한다.

N-1에서 바깥만 채워진 상황에서, 만약 안쪽을 연결시킬 수 있으면 이렇게 연결시킨 것까지 비교한다.

 

같은 원리로, DP[N][2]에 대한 점화식은 다음과 같다. DP[N][1]과 논리가 같으므로, 추가적으로 설명하지는 않겠다.

• DP[N][2] = min(DP[N-1][0]+1, DP[N-1][1]+1)

문제는 주어진 상황은 단순한 '막대'를 구하는 것이 아니라 원형으로 첫 점과 끝점도 연결될 수 있다는 점이다. 따라서 첫 점과 끝 점의 안팎이 연결되는지의 여부에 따라 총 4개의 경우를 나눴다.

• 연결되지 않는다: 첫째 칸에서는 DP[1]에 대해 초기설정을 해준 뒤, 그대로 점화식을 이용한 DP를 돌린다. 이때의 결과는 DP[N][0]
• 바깥쪽만 연결된다: DP[1][1]은 불가능하다(바깥쪽은 무조건 첫째 칸에서 끝나므로). 이를 설정한 뒤, 그대로 DP를 돌린 뒤, 첫째 바깥 칸과 연결된 마지막 바깥 칸을 처리하지 않은 DP[N][1]이 이 경우에서의 답이다.
• 안쪽만 연결된다: 위와 똑같은 이유로 DP[1][2]가 불가능하고, DP[N][2]가 이 경우의 답이 된다.
• 안팎 둘다 연결된다: DP[1][1]과 DP[1][2] 모두 불가능해지고, 마지막 칸은 이미 결정나있으니 N-1번째 칸까지만 검토한 뒤 답은 DP[N-1][0]으로 구할 수 있다.

이 네 가지 값 중 최솟값이 전체 정답이 된다.

사실 위 코드에서 반복되는 부분을 함수로 처리했으면 더 간단한 코드가 되었을 것인데, 경우들이 복잡해서 함수로 통일시킬 생각을 미처 하지 못하고 코드를 짜서 몇배로 길어진 것 같다...