[프로그래머스] 동적계획법 - N으로 표현 문제 풀이 (feat.JS)

오늘은 프로그래머스에서 처음 문제를 풀게된 내용인 동적계획법(Dynamic Programming)의 문제 중 N으로 표현 문제 풀이를 해보겠습니다. 언어는 JavaScript를 활용하여 풀겠습니다.

 

 

동적계획법에 대한 문제는 프로그래머스에서 다음과 같이 설명하고 있습니다.

 

 

불필요한 계산을 줄이고, 효율적으로 최적해를 찾아야만 풀리는 문제들입니다.

 

 

효율적인 방법을 찾아 최적해를 찾는 과정으로 JavaScript를 통해 N으로 표현 문제 풀이를 시작하겠습니다.

 

 

프로그래머스 > 동적계획법(Dynamic Programming) > N으로 표현 문제 풀이

 

 

 

 

▲ 문제 정보

• 문제명: N으로 표현
• 문제 난이도: Level 3
• 문제 푼 사람 수: 10140명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

 

▲ 문제 설명

아래와 같이 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과 사칙연산만을 사용해서 number를 만들기 위해 N의 최소 사용 횟수 구하기
• Inputs
  • N: 사칙연산과 함께 연산에 사용될 숫자
  • number: N과 사칙연산을 통해 구해야할 숫자
• Output: N과 사칙연산만으로 number를 구하기 위해 사용되는 N의 최소 개수

 

 

 

 

▲ 제한 사항

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

 

 

• 1 ≤ N ≤ 9
• 1 ≤ number ≤ 32000
• 수식은 괄호와 사칙연산만 가능, 나누기 연산의 나머지는 무시
• 최소값이 8보다 크면 -1을 반환
  • 즉, N의 사용횟수가 8인 경우까지 확인

 

 

 

 

▲ 입출력 예

N	number	return
5	12	4
2	11	3

 

 

 

 

▲ 입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

 

 

 

▲ 알고리즘 만들기

알고리즘을 만들기 전에 이 문제의 포인트를 잡고 가야할 부분이 있습니다.

먼저 숫자 N의 개수에 따라 구할 수 연산의 수을 모두 확인하여야합니다. 즉, N이 1부터 8개까지 사용되는 경우에 대해서 모든 연산의 종류를 체크해보고 그 경우를 확인하여 가장 작은 경우부터 확인하여 number가 만들어진 경우 그 때 사용된 숫자 N의 개수를 반환하는 알고리즘을 활용해보겠습니다.

 

 

먼저 숫자 N의 개수에 따른 연산 방법을 확인해보겠습니다.

 

 

숫자 N 사용 개수	연산 종류
1	N
2	NN, N+N, N-N, N*N, N/N
3	NNN, NN+N, NN-N, NN*N, NN/N, N+N+N, N+N-N, N+N*N, N+N/N, N-N+N, N-N*N, N-N/N ... [1결과(연산)2결과, 2결과(연산)1결과]
4	[1결과(연산)3결과, 2결과(연산)2결과, 3결과(연산)1결과]
...

 

 

위와 같이 모든 연산의 경우를 구해봄으로써 N의 최소 활용을 통한 number 구하는 방법을 확인할 수 있습니다.

 

 

그럼 구현 알고리즘을 위의 내용을 토대로 만들어보겠습니다.

 

 

1. 각 N의 개수별 만들 수 있는 수를 저장하는 자료구조 Set을 만든다.
2. N의 개수를 1씩 증가시키며, N의 개수별 만들 수 있는 수의 리스트를 Set에 저장한다.
   2-1. N의 개수별 만들 수 있는 수는 위 연산 방법 참조.
3. 만들 수 있는 수의 리스트에 number가 포함되어있으면, 현재 개수를 반환한다.
    (만들지 못하였을 경우, -1을 반환한다.)

 

 

 

 

▲ 코드 구현

function solution(N, number) {
    var answer = -1;
    // 1. 각 N의 개수별 만들 수 있는 수를 저장하는 자료구조 Set을 만든다.
    const makeNumberSet = [];

    if(N === number) {
        answer = 1;
    } else {
        // 2. N의 개수를 1씩 증가시키며, N의 개수별 만들 수 있는 수의 리스트를 Set에 저장한다.
        makeNumberSet[1] = new Set().add(N);
        for (let i = 2; i < 9; i++) {
            calculateResult(i);

            // 3. 만들 수 있는 수의 리스트에 number가 포함되어있으면, 현재 개수를 반환한다.
            //    (만들지 못하였을 경우, -1을 반환한다.)
            if (makeNumberSet[i].has(number)) {
                answer = i;
                break;
            }
        }
    }
    
    // 2-1. N의 개수별 만들 수 있는 수는 위 연산 방법 참조.
    function calculateResult(count) {
        makeNumberSet[count] = new Set();
        let connectValue = N.toString();
        for(let i = 1; i < count; i++) {
            connectValue += N.toString();
            const [left, right] = [i, count-i];
            for(let leftValue of makeNumberSet[left]) {
                for(let rightValue of makeNumberSet[right]) {
                    makeNumberSet[count].add(leftValue + rightValue);
                    makeNumberSet[count].add(leftValue - rightValue);
                    makeNumberSet[count].add(leftValue * rightValue);
                    if(rightValue !== 0) {
                        makeNumberSet[count].add(Math.floor(leftValue / rightValue));
                    }
                }
            }
        }
        makeNumberSet[count].add(parseInt(connectValue));
    }

    return answer;
}

 

 

 

 

▲ 채점 결과

 

 

프로그래머스에서 N으로 표현 문제 풀이는 정확성 테스트 케이스 9개를 모두 통과하여 완료하였습니다.

역시, 동적계획법 문제는 알고리즘을 어떻게 만들어내는지가 정말 중요한 포인트라고 생각됩니다. 그럼 이 포인트를 참고하시어 계속 문제 풀이 이어나가보겠습니다.