[python] Baekjoon 1006 : 습격자 초라기

문제 - Baekjoon 1006 : 습격자 초라기

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

1006번: 습격자 초라기

핵심

"특수소대 최소 배치 계산"

내용

두 행으로 구성된 n개의 열로 이루어져 있으며, 각 칸에는 적의 수가 주어집니다. 목표는 주어진 조건 하에서 특수 소대를 배치하여 모든 구역을 적절히 커버하는 데 필요한 최소 소대 수를 계산하는 것입니다. 특수 소대는 인접한 두 구역을 동시에 커버할 수 있으며, 한 소대가 커버할 수 있는 적의 총 수는 m을 초과할 수 없습니다.

 

coding test

코드

def solve(dp_state):
    # dp 테이블 초기화. 4가지 상태를 갖고, 각 상태는 n+1의 길이를 갖습니다.
    dp = [[2 * n] * (n + 1) for _ in range(4)]
    dp[dp_state][-1] = 0  # 선택된 상태의 마지막 구역을 0으로 초기화

    for index in range(n):
        for state in range(4):
            # 각 상태에 따라 이전 구역에서의 최소 소대 수를 현재 구역에 적용
            dp[0][index] = min(dp[0][index], dp[state][index - 1] + int(state & 1 == 0) + int(state & 2 == 0))
        # 현재 구역과 인접 구역 모두를 커버할 수 있는 경우를 확인
        if enemy[0][index] + enemy[1][index] <= m:
            dp[0][index] = min(dp[0][index], dp[0][index - 1] + 1)
        # 현재 구역과 다음 구역(첫 번째 행)을 커버할 수 있는 경우를 확인
        if index < n - 1 and enemy[0][index] + enemy[0][index + 1] <= m:
            dp[1][index] = min(dp[0][index - 1] + 2, dp[2][index - 1] + 1)
        # 현재 구역과 다음 구역(두 번째 행)을 커버할 수 있는 경우를 확인
        if index < n - 1 and enemy[1][index] + enemy[1][index + 1] <= m:
            dp[2][index] = min(dp[0][index - 1] + 2, dp[1][index - 1] + 1)
        # 두 행의 현재 구역과 다음 구역을 모두 커버할 수 있는 경우를 확인
        if index < n - 1 and enemy[0][index] + enemy[0][index + 1] <= m and enemy[1][index] + enemy[1][index + 1] <= m:
            dp[3][index] = dp[0][index - 1] + 2
    return dp

# 테스트 케이스 수행
for _ in range(int(input())):
    n, m = map(int, input().split())  # n: 구역 수, m: 최대 커버 가능한 적의 수
    enemy = [[*map(int, input().split()), 0] for _ in range(2)]  # 각 행의 적의 수
    result = solve(0)[0][n - 1]  # 기본 상태에서 최소 소대 수 계산

    # 첫 번째와 마지막 구역이 함께 커버 가능한 경우의 최소 소대 수 계산
    if enemy[0][0] + enemy[0][n - 1] <= m:
        dp_temp = solve(1)
        result = min(result, dp_temp[2][n - 2] + 1, dp_temp[0][n - 2] + 2)
    if enemy[1][0] + enemy[1][n - 1] <= m:
        dp_temp = solve(2)
        result = min(result, dp_temp[1][n - 2] + 1, dp_temp[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)  # 계산된 최소 소대 수 출력

코드의 핵심 구성

1. solve 함수:

• 역할: 각 구역을 어떻게 커버할지에 따라 가능한 모든 상태를 고려하여 최소 소대 수를 계산합니다.
• 동작 방식:
  • dp 배열을 초기화하여 각 상태별로 각 구역까지 필요한 최소 소대 수를 저장합니다. 네 가지 상태는 다음과 같습니다:
    1. 현재 구역을 새로운 소대로 커버하는 경우.
    2. 현재 구역과 다음 구역(첫 번째 행)을 함께 커버하는 경우.
    3. 현재 구역과 다음 구역(두 번째 행)을 함께 커버하는 경우.
    4. 두 행의 현재 구역과 다음 구역을 모두 커버하는 경우.
  • 각 상태에 따라 이전 구역에서의 최소 소대 수를 기반으로 현재 구역의 최소 소대 수를 계산합니다.

2. 메인 로직:

• 역할: 테스트 케이스에 대해 입력을 받고, solve 함수를 호출하여 결과를 계산하고 출력합니다.
• 동작 방식:
  • 각 행의 적의 수를 입력받습니다.
  • 기본 상태(첫 번째 상태)에서 시작하여 최소 소대 수를 계산합니다.
  • 특별한 경우(첫 번째와 마지막 구역이 함께 커버 가능한 경우)를 추가로 고려하여 결과를 최적화합니다.

코드의 주요 고려 사항

• 동적 프로그래밍(Dynamic Programming): 이 문제는 동적 프로그래밍을 통해 효율적으로 해결됩니다. 각 구역을 커버하는 데 필요한 최소 소대 수는 이전 구역의 상태에 따라 달라지므로, 이를 고려하여 각 구역별로 최적의 해를 찾습니다.
• 상태 고려: 각 구역을 커버하는 다양한 방법(상태)을 고려해야 합니다. 이는 각 구역이 독립적으로 커버될 수도 있고, 인접한 구역과 함께 커버될 수도 있음을 의미합니다.
• 경계 조건 처리: 첫 번째와 마지막 구역이 특별한 경우를 구성할 수 있으므로, 이를 별도로 처리합니다.

image