백준 2293 동전 1
동전 1
문제는 백준에서 확인 할 수 있다.
✔ 접근방법
- DP
- (k+1)개의 인덱스를 가진 dp 배열 생성
- dp[i]는 숫자 i를 만들기위한 경우의 수
- 점화식
3-1.dp[i] = dp[i] + dp[i-(사용하고자하는 동전)]
입력받은 동전을 순회하면서 dp배열을 생성하면, 답을 얻을 수 있다.
✔ 코드
import sys
def solution(arr, k):
dp = [ 0 for _ in range(k+1) ]
'''
dp[idx]는
arr의 i번째 인덱스까지 루프를 돌았을 때
idx를 만족하는 조합의 수
'''
for i in arr:
for idx in range(len(dp)):
if idx - i == 0:
dp[idx] += 1
elif idx - i < 0:
continue
else:
dp[idx] = dp[idx]+dp[idx-i]
# print(dp)
return dp
if __name__ == "__main__":
n, k = map(int, input().split())
arr = []
for _ in range(n):
arr.append(int(sys.stdin.readline().rstrip()))
arr.sort()
ret = solution(arr, k)
print(ret[-1])
☝ 팁
처음에는 DFS 백트래킹을 해야하나 생각하고 접근하였다.
하지만, dp문제 였고 점화식 세우기가 어려웠다.
아래는 점화식 이해에 참고했던 포스팅
https://velog.io/@juno7803/BOJ-2293-%EB%8F%99%EC%A0%84-1
Author And Source
이 문제에 관하여(백준 2293 동전 1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@aszxvcb/백준-2293-동전-1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)