[알고리즘/DP] 2293번 : 동전 1 - python

링크 : https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

---

• 문제
• 소요시간: 35분 실패

---

• 설계하기(접근방법) 

1. 입력받기

동전과 목표를 입력받는다

 

2. 구현하기

dp인줄 모르고 풀때는 아이디에이션을 못했고

dp인줄 알고도 몰랐다

 

이 문제는

작은 동전부터 각 dp를 순회하면서

경우의 수를 추가해 주는 방식으로 푸는 것이다

 

1원 동전의 경우

dp[1]부터 dp[10]까지

가능한 경우의 수가 1개씩이므로

1, 11, 111 ....

1로 초기화 해준다

 

그 다음 2원 동전의 경우 

가능한 경우인 2원부터

dp[2] = 앞선 1원의 11과 2일 것이다

 

dp[4]의 경우는 어떠할까?

dp[2] 케이스 [11, 2]에서 1원씩 추가가된 케이스인

1111, 112

2만으로 이루어진 새로운 2 + 2 가 나타난다

 

dp[6]의 경우도

dp[4]의 케이스에서 1원씩 2번 추가된 케이스와

2원만으로 이루어진 케이스가 나타난다

 

즉 각 x원을 순회할때마다

dp[i] = dp[i] + dp[i-x]로 초기화해주면 된다

 

3. 출력하기

dp[target]을 출력한다

 

 

---

• 코드(출력)

n, target = map(int, input().split())

money_bag = []
for i in range(n):
    money_bag.append(int(input()))

dp = [0 for _ in range(target + 1)]
dp[0] = 1

for i in money_bag:
    for j in range(i, target + 1):
        dp[j] += dp[j - i]

print(dp[target])

---

• 얻어갈 부분

1. dp 문제는 아이디어가 떠오르지 않으면 어렵다. dp 문제인지 먼저 파악하는 눈도 길러야겠다