[프로그래머스-42895] N으로 표현

[DP-N으로 표현]

프로그래머스

문제 설명

N과 사칙연산만으로 number를 표현할 수 있을 때, N 사용 횟수의 최솟값 리턴하기

ex) N=5, number=12

12 = 5+5+(5/5)+(5/5)

12 = 55/5 + 5/5

12 = (55+5)/5 → 3

 

제한 사항

• N은 1 이상 9 이하이다.
• number는 1 이상 32,000 이하이다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시한다.
• 최솟값이 8보다 크면 -1을 return

 

문제 접근

DP 유형이어서 나온 결과에 대한 N의 사용횟수를 넣어서 계산하는 방법 등 고민했지만, 규칙이 떠오르지 않아 다른 분들의 풀이를 참고했다.

DP 규칙을 잘 찾아야 풀 수 있는 문제인 것 같다.. DP[N의 사용 횟수]로 구해서 접근할 수 있다.

 

위 예제를 이용해보면,

DP[1] = 5를 1번만 사용 = {5}

﹡2개 이상부터는 5를 이어붙일 수 있는 것을 고려해야 한다!

 

DP[2] = 5를 2번 사용 = {55, 5+5, 5/5, 5*5, 5-5} = {55, DP[1]+DP[1], DP[1]/DP[1], DP[1]*DP[1], DP[1]-DP[1]}

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

 

DP[3] = 5를 3번 사용 = {555, DP[1]+DP[2], DP[1]/DP[2], DP[1]*DP[2], DP[1]-DP[2], DP[2]+DP[1], DP[2]/DP[1], DP[2]*DP[1], DP[2]-DP[1]} = 

{555,

// DP[1] + DP[2]

5+55, 5/55, 5*55, 5-55, 5+10, 5/10, 5*10, 5-10, 5+1, 5/1, 5*1, 5-1, 5+25, 5/25, 5*25, 5-25, 5+0, 5/0, 5*0, 5-0,

// DP[2] + DP[1]

55+5, 55/5, 55*5, 55-5, 10+5, 10/5, 10*5, 10-5, 1+5, 1/5, 1*5, 1-5, 25+5, 25/5, 25*5, 25-5, 0+5, 0/5, 0*5, 0-5}

= {555, 60, 0, 275, -50, 15, 50, -5, 6, -20, 5, 4, 30, 125, INF, 11, 2, -4, 20}

 

DP[4] = 5를 4번 사용 = {5555, DP[1]+DP[3], DP[1]/DP[3], DP[1]*DP[3], DP[1]-DP[3], DP[2]+DP[2], DP[2]/DP[2], DP[2]*DP[2], DP[2]-DP[2], DP[3]+DP[1], DP[3]/DP[1], DP[3]*DP[1], DP[3]-DP[1]}

 

즉, 점화식을 구하면 DP[i] = {N.repeat(i), DP[1](+,/,*,-)DP[i-1], DP[2](+,/,*,-)DP[i-2], ... , DP[i-1](+,/,*,-)DP[1]}

 

코드

function solution(N, number) {
    if(N === number) return 1; // N이 number인 경우 바로 1 리턴
    
    // dp[N이 사용된 횟수] = {사용 횟수로 만들 수 있는 수의 집합}
    const dp = Array.from({length: 9}, () => new Set());
    dp[1].add(N); // 1번 사용하여 만들 수 있는 수는 N밖에 없음
    
    for(let i=2;i<=8;i++) {
        dp[i].add(Number(String(N).repeat(i))); // 사칙연산 없이 숫자를 이어 붙이기
        for(let j=1; 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(Math.floor(num1/num2));
                }
            }
        }
        if(dp[i].has(number)) {
            return i;
        }
    }
    return -1;
}