프로그래머스 동적계획법: N으로 표현 javascript

문제링크

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

함수설명

함수는 두 자연수 N과 number를 입력으로 받습니다.
N은 1 이상 9 이하의 수입니다.

 

숫자 N과 사칙연산만을 사용하여
number를 만드는데 필요한 N의 최소 개수를 반환해야 합니다.
만약 그 수가 8보다 크다면 -1을 반환합니다.

정답코드

const solution = (N, number) => {
    if (number === N){
        return 1
    }

    const memo = [...Array(9)].map(x => new Set());
    memo[1].add(N);

    for (let i = 2; i < 9; i++){
        memo[i].add(Number(`${N}`.repeat(i)));
        for ( j = 1; j <= i / 2; j++){
            memo[j].forEach(numFirst => {
                memo[i - j].forEach(numSecond => {
                    [numFirst + numSecond,
                     numFirst - numSecond,
                     numSecond - numFirst,
                     numFirst * numSecond,
                     Math.floor(numFirst / numSecond),
                     Math.floor(numSecond / numFirst)]
                        .filter(x => x > 0 && !memo[i -1].has(x))
                        .forEach(y => memo[i].add(y));
                });

            });
            if(memo[i].has(number)){
                return i
            }
        }
    }

    return -1
    }

해설

이 문제는 전형적인 동적 계획법 문제입니다.

DFS나 BFS와 같이 모든 독립적인 결과를 만들면 성능 문제상 실패합니다.
결과를 구성하는 과정에서 나오는 값을 차곡차곡 저장하면서 이용해야 합니다.

 

1. 9개의 집합을 담는 배열 memo를 생성합니다.

 

각 집합에는 N을 해당 집합의 인덱스 개수만큼 사용하여
만들 수 있는 수를 저장합니다.

• memo [3]에는 N '세 개'로 만들 수 있는 수들이 저장됩니다.

2. memo[i]까지의 집합들을 이용해 memo [i+1]에 들어가는 집합의 원소들을 만듭니다.

 

예를 들어, N이 5라고 합시다.
1개의 N으로 만들 수 있는 수는 5 하나뿐입니다.
2개의 N으로 만들 수 있는 수는 5 + 5, 5 - 5, 5 * 5, 5 / 5, 55로 총 5개입니다.

 

각 과정별로 더하기, 빼기, 곱하기, 나누기, 이어쓰기를 할 수 있습니다.
그러므로, memo[i+1]에는 memo [i]의 원소들 각각에 대해 위 5개의 연산을 수행하여 얻은 값을 넣어줍니다.

 

위와 같이 생각하고, 코드를 작성하자 테스트 케이스는 통과했으나

제출 결과는 불합격이었습니다.

memo [i +1]의 원소를 모두 구하기 위해선
memo [i], memo [1] 뿐만 아니라
두 인덱스를 더했을 때 i + 1 이 되는 모든 두 집합 원소들의 조합을 구해주어야 했습니다.

 

이를 통해 문제를 통과할 수 있었습니다.