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

문제

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

 

사용 알고리즘

- 동적계획법 (Dynamic Programming)

해결방법

• dp 즉, 메모이제이션을 사용한다
• N = 5 일 때, 
  • dp[N의 개수] = 만들 수 있는 정수의 집합
  • dp[1] = 5
  • dp[2] = 10, 0, 25, 1, 55 
    
    • 5+5, 5-5, 5*5, 5/5, 55
  • dp[3] = 3개의 5로 만들 수 있는 정수 집합
              = dp[1] 과 dp[2]의 연산 결과 집합 
              = [5] (+, -, *, / ) [10, 0, 25, 1, 55]
    
    
  • dp[4] = 4개의 5로 만들 수 있는 정수 집합
              = dp[1] X dp[3] + dp[2] X dp[2]
    
    
  • dp[5] = 5개의 5로 만들 수 있는 정수 집합
              = dp[1] X dp[4] + dp[2] X d[3]
• -, /의 경우 앞 뒤가 바뀌면 결과값이 바뀌는데, 이를 calFunc에서 추가해주었기 때문에 dp[3]Xdp[2] 혹은 dp[4]Xdp[1] 등의 연산은 하지 않아도 된다.
• 이런 식으로 dp[8]까지 정수 집합을 구하면 되는데, 구하는 중에 만들어야 하는 number가 만들어지면 연산을 멈추고 해당 층이 몇 층인지 return 해주면 된다

문제예시 1

소스코드

사용언어 : javascript

const calcFuncs = [(a, b) => a + b, 
                    (a, b) => a * b, 
                    (a, b) => a - b,
                    (a, b) => b - a,
                    (a, b) => Math.floor(a / b),
                    (a, b) => Math.floor(b / a)
                  ];

function getCalcRes(nth, dp, N) {
    let dpNth = new Set(); // dp[nth]
    dpNth.add(Number(String(N).repeat(nth))); // 55, 555, 5555
    
    for (let i = 1; i <= parseInt(nth/2); i++) {
        for (const num1 of dp[i].values()) {
            for (const num2 of dp[nth - i].values()) {
                for (const cf of calcFuncs) {
                    const result = cf(num1, num2);
                    dpNth.add(result);
                }
            }
        }
    }
    return dpNth;
}

function solution(N, number) {
    if (N === number) {
        return 1;
    }
    
    const dp = [];
    dp[1] = new Set([N]);
    
    for (let i = 2; i <= 8; i++) {
        dp[i] = getCalcRes(i, dp, N);
                
        if (dp[i].has(number)) {
            return i;
        }
    }
    
    return -1;
}

calFuncs

* 함수 배열

* js에선 함수를 배열로 만들어서 선언할 수 있다. 이 경우 반복문과 함께 사용해서 쓰면 된다.

 

String.repeat

* 문자열 반복 반환 함수

* 해당 문제에서 N을 사칙연산말고도 그냥 연달아 붙여서 만드는 것도 가능인데, 이 때 repeat 함수를 활용해주면 간단하게 만들 수 있다.

dpNth.add(Number(String(N).repeat(nth))); // 55, 555, 5555

 

한줄평

javascript에서 배열안에 함수를 넣을 수 있다는게 가장 놀라운 부분이었다.

그리고, 해당 문제의 dp 점화식을 찾는게 생각보다 까다로웠음.

내가 풀 때는 

dp[1] 

dp[2] = dp[1] X d[1]

dp[3] = dp[2] X dp[1]

dp[4] = dp[3] X dp[1]

. . .

해당 케이스만 생각해서, , 정답에 도달하지 못했다. ; ) 

 

참고 블로그

https://ha-young.github.io/2021/algorithm_javascript/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-N%EC%9C%BC%EB%A1%9C%ED%91%9C%ED%98%84_lv3_dp/