코딩하는 해맑은 거북이
[Python] 거스름돈 - 프로그래머스 (DP) 본문
해당 글은 프로그래머스 Level3 문제 '거스름돈'을 다룬다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/12907
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
설명
다이나믹 프로그래밍 알고리즘으로 풀 수 있는 문제이다.
거스름돈 금액을 동전의 숫자만큼 계속해서 누적해서 경우의 수를 구하고 n번째 dp값을 반환해주면 된다.
코드
def solution(n, money):
dp = [0]*(n+1)
dp[0] = 1
for coin in money:
for price in range(coin, n+1):
dp[price] += dp[price-coin]
return dp[n]%1000000007
'코딩테스트' 카테고리의 다른 글
| [Python] 카드 구매하기 - 백준 (DP) (0) | 2023.01.05 |
|---|---|
| [Python] 스타트와 링크 - 백준 (DFS) (0) | 2023.01.04 |
| [Python] 베스트앨범 - 프로그래머스 (0) | 2023.01.04 |
| [Python] 줄 서는 방법 - 프로그래머스 (0) | 2023.01.03 |
| [Python] 전력망을 둘로 나누기 - 프로그래머스 (BFS) (0) | 2023.01.03 |
Comments