1006 : 습격자 초라기

Contents

1006 : 습격자 초라기#

  • https://d2gd6pc034wcta.cloudfront.net/tier/18.svg 티어

  • 초보자 좌절 전용 문제

  • 예전에 한 번 본적 있던 거 같은데 다시 풀어본다.

시간제한

메모리제한

정답비율

2초

512MB

19.8%

문제#

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

https://www.acmicpc.net/upload/201003/dfck3232_34g7t9f4gp_b.jpg

Fig. 14 숫자는 각 구역의 번호#

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

  1. 한 특수소대는 침투한 구역 외에, 인접한 한 구역 더 침투할 수 있다. (같은 경계를 공유하고 있으면 인접 하다고 한다. 위 그림에서 1구역은 2, 8, 9 구역과 서로 인접한 상태다.) 즉, 한 특수소대는 한 개 혹은 두 개의 구역을 커버할 수 있다.

  2. 특수소대끼리는 아군인지 적인지 구분을 못 하기 때문에, 각 구역은 하나의 소대로만 커버해야 한다.

  3. 한 특수소대가 커버하는 구역의 적들의 합은 특수소대원 수 W 보다 작거나 같아야 한다.

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

첫째 줄에는 (구역의 개수)/2 값 N과 특수 소대원의 수 W가 주어진다. (1 ≤ N ≤ 10000, 1 ≤ W ≤ 10000).

둘째 줄에는 1~N번째 구역에 배치된 적의 수가 주어지고, 셋째 줄에는 N+1 ~ 2N번째 구역에 배치된 적의 수가 공백으로 구분되어 주어진다. (1 ≤ 각 구역에 배치된 최대 적의 수 ≤ 10000) 단, 한 구역에서 특수 소대원의 수보다 많은 적이 배치된 구역은 존재하지 않는다. (따라서, 각 구역에 배치된 최대 적의 수 ≤ W)

출력

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

think#

dp문제이니깐 문제를 작은 것으로 나누는 최적의 원리랑 memorization을 이용해야할 것이다.

  1. 점화식을 세워보고

  2. 이전의 결과물이 뒤에 활용될 수 있으려면 최적의 원리. 그 순간의 최적이 뒤의 최적이 되어야한다.

  3. 그리고 이에 대해서 저장을 해서 계산효율성을 높여야한다.

여기서 최적이 되어야할 부분은 무엇일까?

python#

import sys, os

problem_num = "1006"

path = os.getcwd() + f"\\txt\\{problem_num}" + ".txt"
sys.stdin = open(path, "r")
input = sys.stdin.readline

class PentagonAttack:
    def __init__(self, n, w, enemies):
        self.n = n
        self.w = w
        self.enemies = enemies
        self.dp = [[-1] * (2 * w * n + 1) for _ in range(n + 1)]

    def solve(self):
        result = self.min_special_forces(self.n, 0)
        return result

    def min_special_forces(self, remaining_sections, current_enemy_sum):
        if remaining_sections == 0:
            return 0

        if self.dp[remaining_sections][current_enemy_sum] != -1:
            return self.dp[remaining_sections][current_enemy_sum]

        # 특수 소대원이 0명일 때는 침투를 하지 않음
        min_special_forces_needed = self.min_special_forces(
            remaining_sections - 1, current_enemy_sum
        )

        # 현재 구역의 최대 적 수와 특수 소대원 수 중 작은 값을 선택
        max_enemies = min(self.w, self.enemies[remaining_sections - 1]) + 1

        # 특수 소대원을 배치하거나 배치하지 않는 경우 중 최소값 선택
        for i in range(max_enemies):
            min_special_forces_needed = min(
                min_special_forces_needed,
                self.min_special_forces(remaining_sections - 1, current_enemy_sum + i)
                + (i > 0),
            )

        self.dp[remaining_sections][current_enemy_sum] = min_special_forces_needed
        return min_special_forces_needed


# 테스트 케이스 입력 및 실행
T = int(input())
for _ in range(T):
    N, W = map(int, input().split())
    enemies1 = list(map(int, input().split()))
    enemies2 = list(map(int, input().split()))

    # 두 구역의 적을 합쳐서 하나의 리스트로 만듦
    enemies = enemies1 + enemies2

    # 클래스 생성 및 실행
    pentagon_attack = PentagonAttack(N, W, enemies)
    result = pentagon_attack.solve()
    # 결과 출력
    print(result)

0
Contents