[백준 2293] 동전 1 - python (solved.ac - 골드 5)

 

dp[j]+=dp[j-i]

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

 

2293번: 동전 1

풀이

문제를 보았을때 알수있는 힌트

문제를 보고 반복도 많이 해야하고 시간초과가 날것같다는 생각이 든다면 아마 다이나믹 프로그래밍 문제겠구나 생각을 해야할것같다. 처음에는 dfs로 풀어 보려고 했으나 시간 초과..

dp라고 생각하고 조건을 찾아보니 1부터 10까지 나올수있는 경우의 수를 천천히 계산을 해보았다.

1의 경우

1-> 1개 1

2의 경우 

1-> 1개 1+1

2-> 1개 2

3의 경우

1-> 1개 1+1+1

2-> 1개 1+2

4의 경우

1-> 1개 1+1+1+1

2-> 2개 1+1+2, 2+2

 

이를 통해 보면 4의 경우가 2의 경우에 +2를 추가 한것과 똑같은 모양이 된다. 

dp로 식을 적으면 (j의 경우) dp[j]+=dp[j-2] 가 된다.

이렇게 문제를 풀면 답을 맞출수있다.

import sys
input= sys.stdin.readline


n,k = map(int,input().split())
n_list= []
dp = [0 for _ in range(k+1)]
dp[0]=1
for i in range(n):
    n_list.append(int(input()))

for i in n_list:
    for j in range(1,k+1):
        if j-i >= 0:
            dp[j]+=dp[j-i]
print(dp[k])

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2293.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리