BOJ 9084 [동전]

jj·2022년 6월 23일
0

알고리즘-문제

목록 보기
34/35

문제

문제 보기


동전의 종류가 주어진다. 동전은 1~10000 사이의 값을 갖는다. 숫자 M이 주어질 때 동전으로 M을 만들 수 있는 경우의 수를 구하여라.




풀이


DP는 그냥 여러 유형을 익히는 수 밖에 없는 것 같다. 풀이를 보고 풀었다.


출처

dp table을 1~M 까지 만들고 각 coin에 대해서 순서대로 coin~M 까지의 dp table을 초기화한다. 초기화 하는 방법은 다음과 같다.

if i == coin:
	dp[coin] += 1

if i > coin:
	dp[i] += dp[i-coin]

그럼 n번째 coin까지 진행하면서 dp table은 모든 coin에 대해 초기화된다.

profile
끊임없이 공부하는 개발자

0개의 댓글