자바스크립트 프로그래머스 거스름돈 문제 풀이

📌  문제

 

◾  해설

 

Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.

예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.

• 1원을 5개 사용해서 거슬러 준다.
• 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
• 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
• 5원을 1개 사용해서 거슬러 준다.

거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

 

 

◾  제한 사항

 

• n은 100,000 이하의 자연수입니다.
• 화폐 단위는 100종류 이하입니다.
• 모든 화폐는 무한하게 있다고 가정합니다.
• 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요.

 

◾  입출력 예시

 

n	money	result
5	[ 1, 2, 5 ]	4

 

 

📌  내 풀이

 

규칙 찾다가 시간을 다 썼다 ...

이번 문제는 레퍼런스를 참고하며 아예 공부를 해버렸다 ㅎ

 

📍  Dynamic Programming 동적 프로그래밍

 

2021.10.11 - [개발 공부/Algorithm] - Dynamic Programming 동적 프로그래밍

Dynamic Programming 동적 프로그래밍

 

 

📌  코드 공부

 

 

처음 문제에 접근할 때, fix되는 값은 있어야 겠다는 생각을 했다.

기준이 있어야 기준을 중심으로 나머지 값들을 조합해 원하는 합을 도출해낼 수 있으니까.

그런데 조합으로 경우의 수를 찾고 해당하는 경우의 수의 합을 또 구해야한다고 생각하니 너무 막막했다.

-->  여기서부터 사고의 회로가 꼬인듯

 

일단 기준이 되는 수가 가지고 있는 규칙(?)을 분석해보기로 했다.

n (원하는 합) 을 왼쪽에 정렬하고, 1 2 3 --- 기준을 나열해 반복되는 특성을 찾아보았다.

 

1은 바로        전 수에 1을 계속 더해나가는 특성이 있었고,

2는 바로    전전 수에 2를 계속 더해나가는 특성이 있었고,

3은 바로 전전전 수에 3을 계속 더해나가는 특성이 있었다.  

 

 

경우의 수 관점에서 보면 어떨까 ?

우린 합 5를 만족시키는 [ 1, 2, 5 ] 간 조합된 배열의 개수를 찾고 싶다.  ->  조합하고 싶은 숫자가 정해져있음을 잊지 말자

2가 기준일 때, 2 + 2 + 1 또는 2 + 1 + 1 + 1 의 case 들을 도출해낼 수 있다.

 

그런데 ... 이는 합 3이 갖는 경우의 수와도 동일하다. 2 + 1 또는 1 + 1 + 1

 

다른 경우도 마찬가지다. 합 4를 만족시키는 경우의 수를 찾아보면,

1 + 1 + 1 + 1 또는 2 + 1 + 1 또는 2 + 2 이렇게 총 3개의 case를 도출할 수 있고 

이 안에

✔  1을 기준으로 합 4를 만족시키는 1 + 1 + 1 + 1
✔  2를 기준으로 합 4를 만족시키는 2 + 1 + 1 과 2 + 2 가 포함되어있다.

 

 

우리가 구하고 싶은 건 조합할 수 있는 경우의 수니까, cases를 기준으로 식을 구해보자.

우리는 1을 기준으로 ( 그림과 같이 ) 각 수마다 1개의 경우의 수를 가질 수 있다.

** 인덱스 0에 1을 할당해놓은 이유는, 기준이 되는 숫자가 가질 수 있는 기본적인 경우의 수를 나타내기 위해서이다.

 

 

2를 기준으로 경우의 수를 구해보자.

앞서 1을 기준으로 각 숫자가 가질 수 있는 경우의 수를 담은 배열을 그대로 받아온다.

 

2는                    ( 1 + 1 ) 과       ( 2 )  -> 자기 자신            // array[2] = array[2] + array[0]

3은              ( 1 + 1 + 1 ) 과       ( 2 + 1 )  -> 자기 자신              // array[3] = array[3] + array[1]                         

4는            1 + 1 + 1 + 1 과        2 + ( 1 + 1 ) 과  2 + ( 2 )  -> 자기 자신          // array[4] = array[4] + array[2]    

5는      1 + 1 + 1 + 1 + 1 과  2 + ( 1 + 1 + 1 ) 과  2 + ( 2 + 1 )  -> 자기 자신           // srray[5] = array[5] + array[3] 

 

써놓고보니까 이제서야 반복되는 요소가 보인다 ... 

이 규칙을 스스로 찾을 때까지 문제를 반복적으로 풀어야겠다 어후 ...!

 

 

5는 자기 자신 1을 포함해, 총 4개의 경우의 수를 갖는다. result 가 4니까 !!~!! 정답이다 정답

 

 

📌  코드

 

function solution (n, money){
    let arr = new Array(n+1).fill(0);
    
    arr[0] = 1;
    
    for(let el of money){
    	for(let i=el; i<n+1; i++){
        	arr[i] = arr[i] + arr[i - el];
        }
    }
    
    return arr[n];
}

 

 

📌  깨달은 점

 

반복적으로 구해야하는 작은 값들을 배열에 저장해, 큰 값을 구할 때 지속적으로 참조하는 걸 볼 수 있었다.

공간 복잡도도 적고 ... 써야하는 수식도 적었지만 규칙을 찾는 게 정말 어려운 문제였다.

그리고 조합과 순열, 중복 조합을 자유자재로 사용하지 못해서 더 손을 못대지 않았나 싶다.

더 많은 문제들을 접하면서 뇌에 익도록 노력해야겠다.

그리고 인덱스도 숫자로 활용해서 복잡도를 줄였다고 해야하나 ...? 여튼 발상과 정리 !!! 중요하다.