dp 총 경우의수

BuZZLightyear·2023년 3월 22일
0

정리

목록 보기
38/47

예를 들어 1원, 2원, 5원 을 가지고 총 5원을 만들 수 있는 모든 경우의 수를 따질 때
이미 계산한 값을 저장해놓고 그 저장한곳에서 다시 추가적으로 계산 해 나가는 dp를 활용.

1원으로만 1, 2, 3, 4, 5원을 만들 수 있는 방법
2원을 사용하여 액수를 만들었을 때 사용한 2원의 개수
5원을 사용하여 액수를 만들었을 때 사용한 5원 개수

위에 설명한 3가지 경우를 쉽게 구하는 방법 : 구해야 하는 액수에서 사용해야 하는 동전을 뺏을 때 나오는 값이 그 동전을 몇개 사용했을 때 액수를 만들 수 있는지 모든 경우의 수임.

ex) 2원짜리 동전으로 4원을 만들 경우의 수를 보면 4-2를 하고 2원만드는 경우의 수의 총합이다.

profile
버즈라이트이어

0개의 댓글