[백준 알고리즘: python 3] #1006 - 습격자 초라기

https://www.acmicpc.net/problem/1006

 

정말... 알고리즘 초심자들을 모두 돌아가게 한다는 1006번 문제가 맞았군요. 구글링해보고 공부도 해서 풀고... 결국엔 점화식을 제시해 준 한 블로그를 참고해서 풀었습니다. 1006번 문제는 원타곤의 습격자 초라기가 자신의 특수 소대를 원타곤의 구역에 배치할 때, 최소 필요한 소대 수를 계산하는 문제입니다. 

 

처음에는 점화식을 생각도 안한채로,

 

1. 특수소대가 2곳의 구역을 담당할 수 있을 때, 그 2곳 쌍을 모아서 {구역번호: [함께 담당할 수 있는 구역들]} 의 dict 셋으로 모은 다음,

2. [함께 담당할 수 있는 구역들] 의 길이에 따라 sort시킨 다음에,

3. 길이가 짧은 순서대로(왜냐하면, 길이가 짧을 수록 쌍을 이룰 수 있는 다른 구역의 후보군이 적기 때문에) 먼저 쌍을 성립시키는

 

방식으로 해보려고 했습니다. 써놓은 것을 보면 알겠지만... 그렇게 탄탄한 알고리즘도 아니고 어떠한 변수가 있을 것임에도 뭐 대충 되지 않을까 하는 마음으로 했다가 ... 작살 났습니다. ㅠㅠ

 

Hint!

그러다가 결국 구글링을 하게 됐어요. 다들 잘 안풀리시는 것 같았고, 이것 저것 보다가 정말 잘 정리된 한 블로그를 보게 되었습니다. 멋있으니까 아래에 예쁘게 링크를 걸어볼게요.

https://casterian.net/archives/1356

 

점화식으로 접근하신 분이었어요. 저한테는 점화식으로 풀어냈다는 것이 너무 신선하고 재미있어서, 한자 한자 꼼꼼히 읽어서 코드를 작성하기 시작했습니다. (이해하는게 쉽지는 않았지만요...) 제가 이 블로그에 따로 설명을 드리는 것보다 위 블로그에 들어가셔서 내용을 읽어보시고 생각해 보심이 좋겠습니다. (제가 설명하다가 전달이 잘못될 수도 있을 것 같아서요!) 무엇보다, 이제 다른 알고리즘 문제에도 점화식을 고려해볼 수 있겠다는 생각에 기쁘긴 했는데 어떻게 저런 점화식을 모델링 할 생각을 하는지... 걱정되기도 하네요 ..

 

코드에 약간의 주석을 걸어두었습니다. 위 블로그에는 C++로 작성되어 있습니다. 논리가 거의 비슷하긴 하지만 변수를 두는데 있어서 약간의 차이가 있습니다. 참고해주세요!

 

import sys
# import random
T = int(sys.stdin.readline())
results = []

def recur(start, a, b, c):
    for i in range(start, N):
        # i 열까지 최소
        a[i+1] = min(b[i]+1, c[i]+1)
        if zone1[i] + zone2[i] <= W: a[i+1] = min(a[i+1], a[i]+1)
        if i > 0 and zone1[i-1] + zone1[i] <= W and zone2[i-1] + zone2[i] <= W: a[i+1] = min(a[i+1], a[i-1]+2)

        if i < N-1:
            # 1행은 i+1열, 2행은 i열까지 최소 소대 수
            b[i+1] = a[i+1] + 1
            if zone1[i+1] + zone1[i] <= W: b[i+1] = min(b[i+1], c[i] + 1)

            # 1행은 i열, 2행은 i+1열까지 최소 소대 수
            c[i+1] = a[i+1]+1
            if zone2[i+1] + zone2[i] <= W: c[i+1] = min(c[i+1], b[i] + 1)
    
    return a, b, c


for _ in range(T):
    N, W = map(int, sys.stdin.readline().split())
    # 윗줄 적의 수
    zone1 = list(map(int, sys.stdin.readline().split()))
    # 아랫줄 적의 수
    zone2 = list(map(int, sys.stdin.readline().split()))
    
    # 1행과 2행 모두 i-1열까지 채울 때 최소 소대 수
    a = [0 for _ in range(N+1)]
    # 1행은 i열까지, 2행은 i-1열까지 채울 때 최소 소대 수
    b = [0 for _ in range(N+1)]
    # 1행은 i-1열까지, 2행은 i열까지 채울 때 최소 소대 수
    c = [0 for _ in range(N+1)]
    a[0] = 0
    b[0] = 1
    c[0] = 1
    a, b, c = recur(0, a, b, c)
    res = a[N]
	
    # 윗줄의 0번 열과 끝 열이 쌍을 이룰 수 있을 때 다시 한 번 계산 후 최솟값 갱신
    # 윗줄의 0번 열이 이미 채워졌다고 생각
    if N > 1 and zone1[0] + zone1[N-1] <= W:
        a[1] = 1
        b[1] = 2 # 아랫줄의 0번열, 윗줄의 1번열을 쌍을 이룰 수 없는 채로 2개의 소대를 배치해야함.
        if zone2[0] + zone2[1] <= W: c[1] = 1 # 아랫줄의 0번 열과 1번 열이 쌍을 이룰 수 있는 경우
        else: c[1] = 2
        
        a, b, c = recur(1, a, b, c)
        res = min(res, c[N-1] + 1)
        
    # 아랫줄의 0번 열과 끝 열이 쌍을 이룰 수 있을 때 다시 한 번 계산 후 최솟값 갱신
    # 아랫줄의 0번 열이 이미 채워졌다고 생각
    if N > 1 and zone2[0] + zone2[N-1] <= W:
        a[1] = 1
        c[1] = 2 # 윗줄의 0번열, 아랫줄의 1번열을 쌍을 이룰 수 없는 채로 2개의 소대를 배치해야함.
        if zone1[0] + zone1[1] <= W: b[1] = 1 # 윗줄의 0번 열과 1번 열이 쌍을 이룰 수 있는 경우
        else: b[1] = 2
        
        a, b, c = recur(1, a, b, c)
        res = min(res, b[N-1] + 1)

    # 윗줄과 아랫줄 모두 0번 열과 끝 열이 쌍을 이룰 수 있을 때 다시 한 번 계산 후 최솟값 갱신
    # 윗줄과 아랫줄 모두 0번 열이 이미 채워졌다고 생각
    if N > 1 and zone1[0] + zone1[N-1] <= W and zone2[0] + zone2[N-1] <= W:
        a[1] = 0 # 0열이 이미 채워짐
        b[1] = 1
        c[1] = 1

        a, b, c = recur(1, a, b, c)
        res = min(res, a[N-1] + 2)
    
    results.append(res)

for result in results:
    sys.stdout.write(str(result)+'\n')