728x90
난이도 : Lv. 3
풀이일 : 2412275
https://school.programmers.co.kr/learn/courses/30/lessons/12907
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제


아이디어
- 각 동전에 대해 해당 동전의 가격부터 궁금한 금액까지 해당 동전으로 만들 수 있는 개수 추가
코드
def solution(n, money):
answer = 0
dp = [0] * (n + 1)
dp[0] = 1
for coin in money:
for i in range(coin, n + 1):
dp[i] += dp[i - coin]
answer = dp[n] % 1000000007
return answer
- dp 배열은 구해야할 수까지 생성하기 위해 n+1
- 0원을 만들 수 있는 경우의 수 1 기록
- 각 동전에 대해 반복하며 해당 동전부터 n값까지 동전을 사용해 만들 수 있는 개수 기록
- 답이 너무 커질 경우 처리를 위해 문제 요구사항 수로 나누어 answer 기록 및 반환
제출 결과

느낀점
- 나는 dp 잘 못하는 것 같아 오랜만에 하니까 또 헤매네. 몇 문제 더 풀어봐야지
'알고리즘 > Lv. 3' 카테고리의 다른 글
프로그래머스 12907 거스름돈 자바 풀이 (1) | 2024.12.27 |
---|---|
프로그래머스 12907 거스름돈 자바스크립트 풀이 (0) | 2024.12.27 |
프로그래머스 87694 아이템 줍기 자바 풀이 (0) | 2024.12.18 |
프로그래머스 87694 아이템 줍기 파이썬 풀이 (0) | 2024.12.18 |
프로그래머스 72413 합승 택시 요금 파이썬 풀이 (1) | 2024.11.29 |