23.02.23 파이썬 코딩 퀴즈#169 거스름돈 (프로그래머스 스쿨)

이번 문제는 거스름돈 문제이다.

주어진 n 에 대하여 money 가 종류별로 주어질 때, 해당 n 을 만들 수 있는 money 조합의 개수를 반환해야 한다.

n 이 10만 이하의 자연수 이며, 화폐 단위는 100종류 이하이다. 단순 조합법으로 풀기에는 무리가 있어 보인다.

심지어 정답이 커질 수 있으니 1,000,000,007로 나눈 나머지를 return 하라는 설명도 추가되었다.

 

먼저 입출력 예를 이용하여 경우의 수를 생각해보자.

1원으로는 모든 종류의 거스름돈을 만들 수 있다.

윗 행은 원을 의미한다.

따라서 모든 금액에 대해 + 1이 된다.

참고로 0원인 경우에는 모든 수로 나눈 나머지가 0 이기 때문에 1로 두고 시작하였다.

 

2원으로는 1원을 지불 할 수 없다. 따라서 2원 부터 지불 가능하다.

이때 2원을 지불하는 방법으로 이미 1원으로 지불 가능한 방법이 추가되어 있다. 따라서 2원을 지불하는 방법은 2가 된다.

3원은 1+2원으로 지불 가능하다. 이 또한 이미 1원으로 지불 가능한 방법이 추가되었기에 2가 된다.

3원에서 2원을 뺀 1원을 만드는 방법은 1가지 이다.

4원의 경우는 2원+2원 또는 1원x2개+2원으로 지불 가능하다. 따라서 방법은 3이다

4원에서 2원을 뺀 2원을 만드는 방법이 2가지라는 점이다.

5원의 경우에는 1원+2원x2개, 1원x3개+2원 으로 지불 가능하다. 따라서 방법은 3이다.

5원에서 2원을 뺀 3원을 만드는 방법은 2가지 이다.

이제 이러한 방법으로 만들어진 배열에서 규칙성을 발견 할 수 있다.

즉 dp[현재 지불해야 하는 가격] +=  dp[현재 지불해야 하는 가격 - 화폐 단위] 가 된다.

누적값을 사용하기 때문에 += 가 굉장히 중요하다

이를 코드로 표현하면 위와 같다.

먼저 money 에서 각 잔액을 구한뒤, dp 배열을 돌며 각 index에 값을 전달한다.

이때 중요한 점은 dp[0] = 1 이라는 점이다.

그리고 i 는 (잔액, len(dp) 를 돌면서 값을 누적하여 전달하게 된다.

그리고 최종적으로 dp[n] 을 반환하면 된다.

레벨3 두번째 문제에 도전한건데, 생각보다 삽질을 많이 했다.

과연 이 규칙성을 찾지 않았다면, 이 문제도 시간초과로 인해 시간을 많이 허비했을 듯 하다.