프로그래머스 : N으로 표현 - javascript

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

프로그래머스

 

문제 설명

아래와 같이 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              number          return
5               12                      4                            설명) 12 = (55 + 5) / 5와 같이 5를 4번만 사용하여 표현할 수 있습니다.
2              11                       3                            설명) 11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

 

개념 정리

* 동적계획법(DP)

: 하나의 큰 문제(N번째 답)를 여러 개의 작은 문제(N-a번째 값)로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결

 

https://kmmk808.tistory.com/89

동적계획법

 

접근방법

1. 각 N의 개수별로 만들 수 있는 수를 저장하는 세트 만들기
2. N의 개수별로 만들 수 있는 수를 세트에 저장
3. 만들 수 있는 모든 경우의 수 계산
4. number와 일치하는 경우에는 반환

 

풀이과정

- N은 1 이상 9 이하
- 최솟값(return)이 8보다 크면 -1을 return   =>   N을 1번 사용하는 경우부터 시작하여 N을 8번 사용하는 경우가 존재
- number는 1 이상 32,000 이하
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시 => (+, -, *, /)

 

 

N을 1번 사용하는 경우  =>  N(N을 1번 사용)

N을 2번 사용하는 경우  => NN(N을 1번 2번 사용)
                         N을 1번 사용한 경우와 N을 1번 사용한 결과끼리 사칙연산 => N+N, N*N, N/N, N-N

N을 3번 사용하는 경우  => NNN(N을 1번을 3번 사용하는 경우)
                        (N을 1번 사용하는 경우와 N을 2번사용하는 경우) (N을 2번 사용하는 경우와 N을 1번사용하는 경우)를 사칙연산

N을 4번 사용하는 경우   => NNNN(N을 1번을 4번 사용하는 경우)
                      (N을 1번 3번 각각 한번씩 사용), (N을 2번을 두 번), (3번 1번 각각 한번씩 사용) 하는 경우를 사칙연산

...

 

 

=>


ex) 5

1번 사용하는 경우  =>  5
2번 사용하는 경우   => 55, 10, 25, 1, 0

3번 사용하는 경우는 => 555, (5와 5를 2번사용하는 경우), (5를 2번 사용하는 경우와 1번사용하는 경우)를 사칙연산

4번 사용하는 경우는 => 5555, (5를 1번 3번 각각 한번씩 사용), (5을 2번을 두 번), (3번 1번 각각 한번씩 사용) 하는 경우를 사칙연산

 

 

다른 분의 풀이

function solution(N, number) {
    // N을 사용하여 만들 수 있는 경우의 수를 저장하는 리스트 생성 (최대 8번까지 사용)
    const list = Array.from({ length: 9 }).map((me, index) => new Set([Number(String(N).repeat(index))]))

    // N을 1부터 8번 사용하는 경우를 탐색
    for (let i = 0; i < list.length; i++) {
        // 만약 현재 N을 사용하여 만들 수 있는 결과 리스트에 number가 있다면 해당 횟수 i를 반환
        if (list[i].has(number)) return i
    }

    // N을 2번 이상 사용하는 경우 계산
    for (let i = 1; i < 9; i++) { // N을 사용하는 횟수 (1부터 8까지)
        for (let j = 1; j < i; j++) { // 첫 번째 숫자의 횟수 (1부터 i-1까지)
            for (let x of list[j]) { // 첫 번째 숫자의 모든 경우
                for (let y of list[i - j]) { // 두 번째 숫자의 모든 경우
                    // 사칙연산을 수행한 결과를 계산하고 리스트에 추가
                    const calc = [a, b, c, d] = [x + y, x - y, x * y, x / y]
                    for (component of calc) list[i].add(component)

                    // 결과가 number와 일치하는지 확인하고 일치하면 해당 횟수 i를 반환
                    if (a === number) return i
                    if (b === number) return i
                    if (c === number) return i
                    if (d === number) return i
                }
            }
        }
    }

    // number를 만들 수 없는 경우 -1 반환
    return -1
}

 

 

 

 

로직은 이해 되는데 어떻게 접근 해야하는지 감이 안잡혀서 다른 사람들의 풀이를 보고 이해해보려고 노력했다.

난이도가 조금 더 쉬운 dp문제를 풀어보면서 익히는 걸로 ...