[ 백준 / 골드5 / 파이썬 Python ] Knapsack Problem ( 14728번-벼락치기, 9084번-동전 )

링크
https://www.acmicpc.net/problem/14728
https://www.acmicpc.net/problem/9084

9084번: 동전

14728번: 벼락치기

Knapsack 알고리즘을 공부하다 보니 이 알고리즘은 두 가지 경우로 나뉘어져 있다는 것을 알게 되었다.
구성원소들의 개수가 여러 개인 경우, 구성원소들의 개수가 하나인 경우이다.
이 글에서 다루는 동전 문제가 여러 개인 경우이며, 벼락치기는 하나인 경우이다.

---

코드 - 벼락치기

---

n,t = map(int,input().split())
chapter = [list(map(int,input().split())) for _ in range(n)]
study = {0:0}
for w,v in chapter:
    tmp = dict()
    for dv,dw in study.items():
        if (sumw := w + dw) < study.get((sumv := v + dv), t + 1):
            tmp[sumv] = sumw
    study.update(tmp)
print(max(study.keys()))

 

풀이 - 벼락치기

---

벼락치기 문제는 학습할 단원은 하나 씩만 존재하며 한 단원을 여러 번 사용할 수 없다. 

study는 { 얻을 수 있는 점수(v) : 사용해야 하는 시간(w) } 으로 구성되어 있는 딕셔너리이다. v점수를 얻기 위해 w만큼 필요하다는 의미이다. 위의 코드대로 따라가면 study에는 단원들의 모든 조합이 담으며 사실상 완전탐색이다. 이 코드에서 주목할 부분은 문법이다. 나도 이번에 처음 보는 문법과 함수들이 많아서 설명이 조금 잘못될 수도 있다.

위의 표현식은 '바다코끼리 연산자'를 사용한 표현식으로 sumw라는 변수를 선언해줌과 동시에 값을 대입하고 사용할 수 있게 해준다.

파이썬 3 일정버전 이상부터 사용가능하다는데 난 이번에 처음 알았다.

 

study라는 딕셔너리에서 키를 이용해 값을 가져오는 메서드이다.

get에는 두 번째 인자가 포함될 수 있는데 이는 첫 번째 인자인 키값이 딕셔너리에 없다면 대신 반환해주는 값이다.

 

딕셔너리의 값을 업데이트 해주는 메서드이다.

tmp라는 딕셔너리에 포함된 키값 중 study에 이미 존재하다면 값을 바꿔주고 없다면 새로 만들어준다.

 

위의 함수들을 사용해서 모든 경우를 비교하여 가장 큰 값을 출력한다. 

 

---

코드 - 동전

---

for _ in range(int(input())):
    n = int(input())
    coin = list(map(int,input().split()))
    target = int(input())
    dp = [0] * (target+1)

    for c in coin:
        if target >= c:
            dp[c] += 1
        for num in range(c+1,target+1):
            dp[num] += dp[num-c]

    print(dp[target])

 

풀이 - 동전

---

동전 문제는 target이라는 값을 만들기 위해서 주어진 동전들을 하나씩 사용하는 것이 아닌 무한대로 사용할 수 있다.

따라서 위와 같은 방법으로는 해결할 수 없고 dp를 사용하였다.

 

여기서 사용하는 dp 아이디어는 간단하다. 

dp[금액] = 금액을 만들 수 있는 가짓수이다. 따라서 주어지는 동전들을 반복하며 도달하는 금액마다 1씩 더해주면 된다.

또한 크기에 따라 변하는 값이 없기 때문에 동전은 굳이 정렬되어 있을 필요가 없다.