냅색 연습-2293 동전1, 1535 안녕

배낭 문제 연습을 시작할 동전 1이다.

먼저, 오랜만에 올리는 PS 일지인 만큼 초심으로 돌아가고자 하여 동적계획법을 연습해보았다.

그리고 언어를 python으로 하였는데, 이전에는 C++로 하였지만 다니는 학교에서 python을 사용하여 python으로 문제를 풀게 되었다.

문법상 구조는 거의 비슷하니 C++에서 python으로 넘어가는 것은 C언어를 처음 배울 때 보다는 어렵지 않았다고 느꼈다.

문제를 분석해보자

n가지 동전이 있다.

각 n가지 동전은 서로 다른 가치를 가지고 있다.

이 동전들을 여러 번 사용하여 k라는 가치를 만드는 방법의 수를 구하는 문제이다.

냅색이라고 하기엔 애매하지만, 냅색이랑 거의 비슷한 구조를 지닌다고 느꼈다. 

문제를 분해하여 생각하면 좋을 것 같다.

dp[k] += dp[k-coin[i]]가 핵심적인 문제 분해이다. k는 어떤 가치이고, coin배열은 동전의 가치를 뜻한다.

즉, dp[k]에 dp[k-coin[i]]를 더한다는 것은 합의 법칙을 이용하여 이 가치를 구성하는 방법의 수를 점화식처럼 나타냈다고 볼 수 있다.

 

여기서 첨언을 하자면 원래 개인적으로 재귀함수 DP를 선호하였으나, bottom-up방식이 수학적으로 더 직관적이란 것을 알게되었고, 앞으로 풀이 방식을 변화시키려 노력하고 있다.

n, k = map(int, input().split())
dp = [0 for i in range(k+1)]
coin = []
for i in range(n):
    coin.append(int(input()))
dp[0] = 1
for i in range(n):
    for j in range(k+1):
        if 0 <= j-coin[i]:
            dp[j] += dp[j-coin[i]]
print(dp[-1])

이걸 재귀로 풀려면 2배의 길이는 나왔을 것이다... 

i를 n만큼 반복하는 이유는, 경우가 겹치지 않기 위해서다. 문제 조건에서 구성은 같지만 순서가 다른 것을 같은 것으로 치는데, 처음에 이걸 무시했다가 반복문 순서를 반대로 써서 처참히 2시간을 버렸다.

 

이제는 "안녕"이다. 가라는 소리가 아니고 문제의 이름이다.

체력을 배낭의 용량이라고 생각하면 된다고 느꼈다.

n = int(input())
hp = list(map(int, input().split()))
happy = list(map(int, input().split()))
dp = [[0 for i in range(101)] for j in range(21)] # 시도수, 닳은 체력
for i in range(1, n+1):
    for j in range(1, 101):
        if hp[i-1] < j:
            dp[i][j] = max(dp[i-1][j-hp[i-1]]+happy[i-1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j] #뒤에 것을 그대로 
m = 0
for j in range(100, 0, -1):
    if dp[n][j] != 0:
        m = dp[n][j]
        break
print(m)

반복문을 돌리면서, 어떤 인사를 선택하는 것과 무시하고 다음 단계로 넘어가거나 하는 선택지를 max를 통해 판단한다.

그리고 출력할 때는 가장 마지막에 있는 값을 출력하기 위하여 다음 반복문을 작성한 것이다.