[BOJ 1006] 습격자 초라기 (P3, DP)

#

문제 정보

  • 난이도 : Platinum 3
  • 체감 난이도 : Platinum 2
  • 알고리즘 : DP

문제 설명

적이 있는 2N 개의 구역이 두 개의 원 모양으로 배치돼 있다.

W명으로 구성된 특수 소대를 침투시켜 모든 적을 커버할 수 있도록 구역 별로 배치하려고 한다.

[규칙 1]

한 특수 소대는 침투한 구역 외에 인접한 구역 한 개를 더 침투할 수 있다.
이때 인접한 구역이라는 것은 같은 경계를 공유하고 있는 구역을 의미한다.

[규칙 2]

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

[규칙 3]

한 구역에는 한 특수 소대만 배치될 수 있다.

이때, 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 구하는 문제이다.

문제 해결

보자마자 2 * N 타일 문제를 떠올렸고, 이전 상태를 기반으로 현재 상태를 결정할 수 있기에 DP를 쓰기로 하였다.

dp[i][j][k] : i번 구역을 보고 있을 때, 배치된 형태가 j이고, 0번 구역의 배치 형태가 k이다.

  • 상태를 조금 과도하게 정의한 느낌이 있는데, 이 부분은 조금 더 관찰 후 최적화 할 수 있을 거 같다.

원형 DP이므로, 첫 번째 상태는 따로 저장해서 (N – 1)번째와 연결 시 참조하기 위해, 위 7가지 상태와 따로 관리하기로 결정하였다.

일단 초기 상태를 모두 정의해주었다.
두 개의 구역을 차지해야 하는 경우, 옆 구역과 현재 구역의 적 수를 고려하여 초기 값을 설정해주었다.

Python
if e1[0] + e2[0] <= w:
    dp[0][1][1] = 1

dp[0][2][2] = 2
dp[0][3][3] = 1
dp[0][4][4] = 1

if e2[0] + e2[-1] <= w:
    dp[0][5][5] = 1

if e1[0] + e1[-1] <= w:
    dp[0][6][6] = 1

if e1[0] + e1[-1] <= w and e2[0] + e2[-1] <= w:
    dp[0][7][7] = 2

이제 반복문을 돌면서 DP 배열을 채워주면 된다.
중첩된 for 문은 첫 번째 구역의 상태이고, for문 내부에서는 이전 구역의 상태를 토대로 현재 구역의 상태를 설정해준다.

Python
for i in range(1, n - 1):
    for j in range(1, 10):
        ...

코드를 조금 더 깔끔하게 작성하기 위해 get_dp_values 함수를 작성했다.

i번째 구역을 계산할 때, i - 1번째 DP 배열을 참조할 때 쓰는 함수인데, i - 1번째 까지는 구역이 모두 채워져야 하므로, dp[i - 1][3] ~ dp[i - 1][6]을 참조하는 경우에는 1을 더하도록 하였다.

Python
def get_dp_values(dp, i, j, types, w):
    wc = [3, 4, 5, 6]
    ret = []
    for x in types:
        val = dp[i][x][j]
        if w and x in wc: val += 1
        ret.append(val)
    return ret

for문 내부 코드는 아래와 같다.

주의해야 할 점이 상당히 많다. 코드가 상당히 복잡하므로 아래 정답 코드를 참고하도록 한다.

  • 추가되는 소대의 수를 정확히 더해줘야 한다.
  • 두 개의 구역을 차지할 때는 적의 수가 소대 인원의 수를 넘어가지 않는지 확인해줘야 한다.
  • (N – 1)번째 구역과 0번째 구역을 합치는 과정에서, 0번째 – 1번째 구역을 한 소대가 차지하는 경우를 처리해주기 위해 일부 케이스의 경우 i == 1은 따로 고려해주어야 한다.

계산이 끝난 후, N – 1번째와 0번째를 연결해주는 작업을 진행했다.

  • N – 1번째와 0번째를 채우는 모든 경우를 고려해주면 된다.
  • 이때는 모든 구역에 소대가 배치돼야 하므로, 3, 4번 케이스의 경우에 빈 구역이 생기지 않도록 추가 소대를 배치해주도록 하자.

정답 코드

Python
def get_dp_values(dp, i, j, types, w):
    wc = [3, 4, 5, 6]
    ret = []
    for x in types:
        val = dp[i][x][j]
        if w and x in wc: val += 1
        ret.append(val)
    return ret

def solve():
    n, w = map(int, input().split())
    e1 = list(map(int, input().split()))
    e2 = list(map(int, input().split()))

    if n == 1:
        if e1[0] + e2[0] <= w:
            print(1)
        else:
            print(2)
        return

    dp = [[[987654321 for _ in range(10)] for _ in range(10)] for _ in range(n + 1)]

    if e1[0] + e2[0] <= w:
        dp[0][1][1] = 1

    dp[0][2][2] = 2
    dp[0][3][3] = 1
    dp[0][4][4] = 1

    if e2[0] + e2[-1] <= w:
        dp[0][5][5] = 1

    if e1[0] + e1[-1] <= w:
        dp[0][6][6] = 1

    if e1[0] + e1[-1] <= w and e2[0] + e2[-1] <= w:
        dp[0][7][7] = 2

    for i in range(1, n - 1):
        for j in range(1, 10):
            dp_vals = get_dp_values(dp, i - 1, j, [1, 2, 3, 4, 5, 6, 7], i != 1)

            if e1[i] + e2[i] <= w:
                dp[i][1][j] = min(dp_vals) + 1

            dp[i][2][j] = min(dp_vals) + 2
            dp[i][3][j] = min(dp_vals) + 1
            dp[i][4][j] = min(dp_vals) + 1

            if e2[i] + e2[i - 1] <= w:
                if i == 1:
                    dp[i][5][1] = 2
                    dp[i][5][2] = 2
                    dp[i][5][4] = 1
                    dp[i][5][6] = dp[0][6][6] + 1

                    dp[i][5][9] = dp[0][6][6] + 1
                else:
                    dp[i][5][j] = min(dp[i - 1][3][j], dp[i - 1][6][j]) + 1

            if e1[i] + e1[i - 1] <= w:
                if i == 1:
                    dp[i][6][1] = 2
                    dp[i][6][2] = 2
                    dp[i][6][3] = 1
                    dp[i][6][5] = dp[0][5][5] + 1

                    dp[i][6][8] = dp[0][5][5] + 1
                else:
                    dp[i][6][j] = min(dp[i - 1][4][j], dp[i - 1][5][j]) + 1

            if e1[i] + e1[i - 1] <= w and e2[i] + e2[i - 1] <= w:
                if i == 1:
                    dp[i][7][1] = 2
                    dp[i][7][2] = 2
                else:
                    dp[i][7][j] = min(get_dp_values(dp, i - 2, j, [1, 2, 3, 4, 5, 6, 7], True)) + 2

    c = []
    x = [1, 2, 3, 4, 5, 6, 7]

    # case 1
    if e1[n - 1] + e2[n - 1] <= w:
        c.append(min(get_dp_values(dp, n - 2, 1, x, True) + get_dp_values(dp, n - 2, 2, x, True)) + 1)

    # case 2
    c.append(min(get_dp_values(dp, n - 2, 1, x, True) + get_dp_values(dp, n - 2, 2, x, True)) + 2)

    # case 3
    if e2[n - 1] + e2[n - 2] <= w:
        c.append(
            min(
                dp[n - 2][3][1],
                dp[n - 2][6][1],
                dp[n - 2][3][2],
                dp[n - 2][6][2],
            ) + 2
        )

    # case 4
    if e1[n - 1] + e1[n - 2] <= w:
        c.append(
            min(
                dp[n - 2][4][1],
                dp[n - 2][5][1],
                dp[n - 2][4][2],
                dp[n - 2][5][2],
            ) + 2
        )

    # case 5
    if e2[n - 1] + e2[n - 2] <= w and e1[n - 1] + e1[0] <= w:
        c.append(
            min(
                dp[n - 2][3][4],
                dp[n - 2][6][4]
            ) + 2
        )

    # case 6
    if e1[n - 1] + e1[n - 2] <= w and e2[n - 1] + e2[0] <= w:
        c.append(
            min(
                dp[n - 2][4][3],
                dp[n - 2][5][3]
            ) + 2
        )

    # case 5 - 2
    c.append(
        min(
            get_dp_values(dp, n - 2, 5, x, True) +
            get_dp_values(dp, n - 2, 6, x, True)
        ) + 2
    )
    c.append(
        min(
            get_dp_values(dp, n - 2, 9, x, True) +
            get_dp_values(dp, n - 2, 8, x, True)
        ) + 1
    )


    # case 7
    c.append(min(get_dp_values(dp, n - 2, 7, x, True)))

    # case 8
    if e1[n - 1] + e1[n - 2] <= w and e2[n - 1] + e2[n - 2] <= w:
        c.append(
            min(
                get_dp_values(dp, n - 3, 1, x, True) +
                get_dp_values(dp, n - 3, 2, x, True)
            ) + 2
        )

    print(min(c))

t = int(input())
for _ in range(t):
    solve()

마무리

상태의 개수가 많지 않으므로 가능한 상태를 모두 고려하여 판단하는 것은 직관적이고 떠올리기 어렵지 않다.

이전에 현재 상태에 대해 6개 상태를 관리해야 하는 DP 문제를 풀어본 적이 있었는데, 이때 크기가 N * 6인 2차원 배열을 선언하여 해결 했던 기억이 있어서 이 문제에도 활용해보았다.

근데 생각했던 거보다 구현이 더 복잡했고 엣지 케이스도 너무 많아서 푸는데 시간이 꽤 걸렸다.

스스로도 깔끔하고 좋은 방법으로 푼 거 같지가 않아, 더 효율적인 방법을 탐구해보려고 한다.

댓글 남기기

Dalmeng's Footprints에서 더 알아보기

지금 구독하여 계속 읽고 전체 아카이브에 액세스하세요.

계속 읽기