Question

dp로 안풀린다고 하였지만 특정 조건으로 정렬하면 dp로 풀립니다.

이 문제를 풀때 그냥 dp를 적용하면 풀리지 않습니다. 그래서 dp로는 풀수 없다고 하는 것 같습니다.

하지만 (최소 피로도 - 소모 피로도)가 작은 순으로 정렬을 먼저 한 다음에 냅색 문제에서 사용하는 dp를 적용시키면 놀랍게도 풀립니다.

여기서 위와같이 정렬하는 이유는 간단하게 설명하면 다음과 같은 느낌입니다. 제가 증명까지는 어려워서..

일단 냅색은 dp의 값을 업데이트할때 왼쪽 위의 값을 가지고 와서 업데이트 한다는 것은 알고 있으실 겁니다.(dp[i][w] = max(dp[i-1][w-wi], dp[i-1][w])에서 dp[i-1][w-wi]를 가져오는 것을 말하는 것입니다.

그런데 이 문제는 왼쪽 위의 값을 바로 가져올 수 없고, (최소 피로도 - 소모 피로도) 만큼 오른쪽으로 이동한 후에야 왼쪽 위의 값을 가져올 수 있습니다.
(테이블을 직접 그려보시면 이해가 되실 겁니다.)

따라서 저 차이가 작은 순으로 먼저 정렬을 해주는 것입니다. 만약 그렇게 정렬하지 않아서 왼쪽 위의 값이 너무 밀려 범위를 벗어나게 되면, 밑에서는 그 값을 가지고 올수 없게 됩니다.

예를들어 k = 8, [[8, 1], [7, 2], [1, 1], [3, 2], [2, 1]] 이라고 하면,
처음에 [8, 1]이 너무 크기 때문에 너무 뒤로 밀리게 됩니다.

즉 dp[1][3] ~ dp[1][7] 까지 전부 0이 되고, dp[1][8]이 되어서야 해당 던전을 방문 할수 있게 되어 dp[1][8]이 1이 되는 것입니다.

그런데 이렇게 밀리면 뒤에서 이 값을 가져올수 없게 되어서 오차가 발생하게 됩니다.

따라서 최소 피로도 - 소모 피로도 가 작은 순으로 정렬한 뒤에 dp를 적용하면 왼쪽 위에서 가져올때 밀려서 못가져오는 경우가 발생하지 않기 때문에 문제가 풀리는 것입니다.

dp로 풀면 n이 커질때 dfs나 순열을 이용하는 방식보다 매우매우 빠르기 때문에 이 방식도 한번 살펴보길 추천드립니다.

작성중인 코드―solution.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(k, dungeons):
    n = len(dungeons)
    dungeons.sort(key=lambda x: (x[0]-x[1]))

    dp = [[0]*(k+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for r in range(1, k+1):
            if dungeons[i-1][0] > r:
                dp[i][r] = dp[i-1][r]
            else:
                dp[i][r] = max(dp[i-1][r], 1 + dp[i-1][r-dungeons[i-1][1]])

    return dp[n][k]

최곱니다 좋아요 누르고 싶은데 못 찾겠네요 ㅜㅜ

기윤호―2023.09.29 18:58
아이디어 감사합니다. 대충보고 막연히 될거라고 생각했는데 정렬까지 해야 된다는건 생각 못했네요.

Tee Mo―2024.10.24 15:55

Answer 1

좋은 아이디어 공유 감사합니다. 증명 과정에서 생각을 보태 보면, 보통 0-1 Knapsack 정답에 i번째 아이템과 j번째 아이템이 포함될 때는 아이템을 고르는 순서가 상관이 없지만 이 문제에선 최소 피로도라는 변수가 추가돼서 일부 순서는 불가능해졌네요. 그런데 어쨌든 i번째와 j번째를 동시에 포함하는 경우가 가능하다면, i번째부터 또는 j번째부터라는 2가지 순서 중에서 (최소 피로도 - 소모 피로도)가 작은 것부터 고르는 순서는 항상 그리디하게 먼저 가능하다는 것을 알 수 있습니다. 가령 i번째를 고르면 남길 수 있는 최솟값이 30이고, j번째는 최솟값이 40이며, (i번째 소모 피로도)+(j번째 소모 피로도)=100이면, 현재 피로도가 최소 130인 때부터 2개를 다 고를 수 있는데 140일 때부터 고를 필요가 없는 것이죠. 그래서 140일 때부터 고르는 반대쪽 순서가 나중에라도 가능해질 수는 있지만 논외로 할 수 있습니다. 결국 어떤 정답이 존재하면 그 정답에서 아이템을 고르는 순서를 (최소 피로도 - 소모 피로도)가 작은 것부터로 고치는 것이 항상 가능하기 때문에, 그 순서로만 문제를 풀어도 무방합니다. 따라서 전처리로 아이템을 정렬해 놓고 그 순서대로 반복문을 순회하면, 기존에 순서 신경 쓰지 않고 순회하던 0-1 Knapsack DP라도 그 순서 그대로 정답을 찾을 수 있게 됩니다. 그 순서가 아닌 다른 순서로 아이템을 고르는 경우에는 정답을 찾는다고 보장하기 어려웠던 문제이지만요. 이러한 그리디 발상에 실패했다면 아이템을 permutation한 모든 경우를 가정하고 정답을 탐색해도 그 중에 정답은 있었겠네요. 한편 DP 테이블 채울 때 작은 것부터 고른다는 말이 좀 헷갈리는데, 현재 피로도 기준으로 피로도를 감소시키며 고른다는 관점에서는 반대로 큰 것부터 고르는 겁니다..

이낙헌

2023.7.26 22:12

dp로 안풀린다고 하였지만 특정 조건으로 정렬하면 dp로 풀립니다.

작성중인 코드―solution.py

기윤호―2023.09.29 18:58

Tee Mo―2024.10.24 15:55

1 개의 답변

기윤호

2023.9.29 19:37

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.