[백준] 1006번 습격자 초라기 - PYTHON, 점화식

[백준] 1006번 습격자 초라기 - PYTHON, 점화식 

 

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

1006번: 습격자 초라기

"""
    습격자 초라기
    https://www.acmicpc.net/problem/1006
    문제
        초라기는 한국의 비밀국방기지(원타곤)를 습격하라는 임무를 받은 특급요원이다. 원타곤의 건물은 도넛 형태이며, 초라기는 효율적인 타격 포인트를 정하기 위해 구역을 아래와 같이 두 개의 원 모양으로 나누었다. (그림의 숫자는 각 구역의 번호이다.)
        초라기는 각각 W명으로 구성된 특수소대를 다수 출동시켜 모든 구역에 침투시킬 예정이며, 각 구역 별로 적이 몇 명씩 배치되어 있는지는 초라기가 모두 알고 있다. 특수소대를 아래 조건에 따라 침투 시킬 수 있다.
        한 특수소대는 침투한 구역 외에, 인접한 한 구역 더 침투할 수 있다. (같은 경계를 공유하고 있으면 인접 하다고 한다. 위 그림에서 1구역은 2, 8, 9 구역과 서로 인접한 상태다.) 즉, 한 특수소대는 한 개 혹은 두 개의 구역을 커버할 수 있다.
        특수소대끼리는 아군인지 적인지 구분을 못 하기 때문에, 각 구역은 하나의 소대로만 커버해야 한다.
        한 특수소대가 커버하는 구역의 적들의 합은 특수소대원 수 W 보다 작거나 같아야 한다.
        이때 초라기는 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 알고 싶어 한다.
    입력
        첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.
        첫째 줄에는 (구역의 개수)/2 값 N과 특수 소대원의 수 W가 주어진다. (1 ≤ N ≤ 10000, 1 ≤ W ≤ 10000).
        둘째 줄에는 1~N번째 구역에 배치된 적의 수가 주어지고, 셋째 줄에는 N+1 ~ 2N번째 구역에 배치된 적의 수가 공백으로 구분되어 주어진다. (1 ≤ 각 구역에 배치된 최대 적의 수 ≤ 10000) 단, 한 구역에서 특수 소대원의 수보다 많은 적이 배치된 구역은 존재하지 않는다. (따라서, 각 구역에 배치된 최대 적의 수 ≤ W)

    출력
        각 테스트케이스에 대해서 한 줄에 하나씩 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 출력하시오.

    예제 입력 1 
        1
        8 100
        70 60 55 43 57 60 44 50
        58 40 47 90 45 52 80 40
    예제 출력 1 
        11
    힌트
        하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 
        그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 
        그러므로 최소 11개 특수 소대를 침투시켜야 한다.
        
    *** 참고 : BOJ 1006  습격자 초라기 https://casterian.net/algo-prob/boj1006.html  (점화식으로 접근하신 분)
               https://nerogarret.tistory.com/20
 
"""

# T = int(input(" 테스트 케이스 T 입력 : "))

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')


""" OUTPUT
   >> 1006_raider.py 
    1
    8 100
    70 60 55 43 57 60 44 50
    58 40 47 90 45 52 80 40
    11
"""

---

수학에서 점화식(漸化式)은 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다.