동적 계획법(Dynamic Programming) / 3 / N으로 표현하기

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

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

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때,

N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을

return 하도록 solution 함수를 작성하세요.

 

제한 사항

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

 

문제 풀이 방법

• 주어지는 N이라는 숫자를 1번 쓰는 경우부터 8번 쓰는 경우까지 봐야한다.(8번보다 많이 사용하면 -1 반환)
• 길이가 9인 배열을 선언해준다(index가 0인 부분은 직관적으로 만들기 위해 빈 인덱스로 둠)
• Q번 사용하는 경우를 useArr[Q]에 넣어준다.(맨 처음에 사칙연산을 사용하지 않은 값들을 저장)
• Set을 사용한 이유는 중복을 방지해 불필요한 연산을 줄이기 위해서 이다.

 

코드

function solution(N, number) {
    const useArr = Array.from(new Array(9), () => new Set());
    if(N === number){
        return 1;
    }
    else{
        useArr.forEach((e, i) => {
            if(i !== 0) e.add(Number(String(N).repeat(i)));
        });
      //  여기서 부터 동적 계획법을 이용하여 연산한다.
      //  i는 다음 수, j는 1부터 시작해 i-j와 조합되어 N이 사용된 횟수를 나타냄
        for(let i=1; i<useArr.length; i++){
            for(let j=1; j<i; j++){
                for(let item1 of useArr[j]){
                    for(let item2 of useArr[i-j]){
                        useArr[i].add(item1 + item2);
                        useArr[i].add(item1 - item2);
                        useArr[i].add(item1 * item2);
                        useArr[i].add(Math.floor(item1 / item2));
                    }
                }
            }
            if(useArr[i].has(number)){
                return i
            }
        }
        return -1
    }
}

 

처음엔 어떻게 풀어야 할지 감이 안잡혀서 다른 분이 작성한 블로그 글을 참고했다.

N을 사용하는 횟수대로 나누는 아이디어를 얻었다.

이렇게 나누니 DP를 사용하는 방법이 머리에서 생각나기 시작했다.