[JS] N으로 표현

dp를 활용해서 해결하였다.

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

 

 

dp[i] 는 N i개로 만들수 있는 숫자들의 모임이다.

 

처음에는 map 자료형을 통해서 { 숫자 -> 숫자를 만드는데 필요한 N의 개수 } 와 같은 방식으로 dp를 구현했었다. 이렇게 dp를 구현하니 문제가 있었다. 자, dp를 채우는 과정을 생각해 보자.

 

편의상 N이라는 말 대신 숫자 5를 써보겠다.

1. 5가 한개일때

 

만들 수 있는 수는 5 하나이다.

 

=> { 5 }

 

2. 5가 2개일때

 

아래와 같은 경우의 수가 나올 수 있다.

 

5 + 5

5 + 5

5 - 5

5 - 5

5 / 5

5 / 5

5 * 5

5 * 5

55

 

=> { 10,0,1,25,55 }

 

잘 보면 사칙연산을 두번씩 한 것을 알 수 있다. 지금은 이해가 안갈 수 있다. 5가 세번째인 경우를 보면 알 수 있을 것이다.

 

10 + 5

5 + 10

10 - 5

5 - 10

10 / 5

5 / 10

10 * 5

5 * 10

...

555

 

즉, dp[i] 를 만들기 위해서는 dp[j] 와 dp[i-j] 를 조합하여 만들어야 함을 알 수 있다. 그리고 555와 같이 N을 여러개 붙인 경우는 특이 케이스로 합쳐주기만 하면 된다.

 

 

 

function solution(N, number) {
    //dp[i] 는 N i개로 만들수 있는 숫자
    const dp = [...Array(9)].map(_=>new Set())
    
    for (let i = 1 ; i <= 8 ; i++) {
        //숫자가 붙여져서 나오는 경우의 수
        dp[i].add(parseInt(String(N).repeat(i)))
        
        //지금까지 구한 dp의 조합으로 새 dp를 만듬
        for(let j=0;j<i;j++){
            for(const num1 of dp[j]){
                for(const num2 of dp[i-j]){
                    dp[i].add(num1*num2)
                    dp[i].add(~~(num1/num2))
                    dp[i].add(num1-num2)
                    dp[i].add(num1+num2)
                }   
            }   
        }
        if(dp[i].has(number)) return i
    }
    
    return -1
}