[프로그래머스] 고득점 키트 - DP1

오늘 푼 문제

 

1. N으로 표현 / Lv.3 / 시간 :  132분(타임오버)

programmers.co.kr/learn/courses/30/lessons/42895?language=javascript

코딩테스트 연습 - N으로 표현

function solution(N, number) {
    var answer = 0;
    let temp = [];
    
    if(N===number) return 1;
    
    for(let i=1;i<=8;i++){
        let num = new Array(i).fill(N).join('')*1;
        if(num===number) return i;
        temp[i-1] = [num]
    };
    for(let i=1; i<8; i++){
        for(let j=0; j<i-j;j++){
            let target1 = temp[j];
            let target2 = temp[i-j-1];
            for(let k=0;k<target2.length;k++){
                let num2 = target2[k];
                for(let r=0;r<target1.length;r++){
                    let num1 = target1[r];
                    if(num2+num1===number) return i+1;
                    temp[i].push(num2+num1);
                    if(num2-num1===number) return i+1;
                    temp[i].push(num2-num1);
                    if(num1-num2===number) return i+1;
                    temp[i].push(num1-num2);
                    if(num2*num1===number) return i+1;
                    temp[i].push(num2*num1);
                    if(Math.floor(num2/num1)===number) return i+1;
                    if(num2) temp[i].push(Math.floor(num2/num1));
                    if(Math.floor(num1/num2)===number) return i+1;
                    if(num1) temp[i].push(Math.floor(num1/num2));
                }
            }
        }
        temp[i] = [...new Set(temp[i])];
    }

    return -1;
}

 

 

헤맸던 부분

 

1. 로직 자체가 씹오바였음;; 어케 접근해야 하는지 몰라서 한참을 헤맴. 

N을 1번 사용해서 만들 수 있는 경우부터 8번 사용해서 만들 수 있는 경우까지 이전 경우와 합집합을 만들어가면 됨

 

2. 이 떄 주의사항은 N을 4번 이상 사용하는 경우부터는 단순히 (n-1번 사용하는 경우) U (1번 사용하는 경우) 로 하면 안됨.

ex) 4번 사용하는 경우는 (3번사용) U (1번사용) 의 경우와 (2번사용) U (2번 사용) 로 만들 수 있고,

    5번 사용하는 경우는 (4번 사용) U (1번 사용), (3번 사용) U (2번 사용) 

    6번 사용하는 경우는 (5번 사용) U (1번 사용), (4번 사용) U (2번 사용), (3번 사용) U (3번 사용) 

   ... 이렇게 확인해야 한다. 이 때 역순 또한 나눗셈과 뺼셈 연산의 경우 고려해줘야 함.

 

3. 테케 2번이 자꾸 틀림. 알고보니 N=1, number=11/ N=2, number=222 처럼 N이 반복되기만 해서 만들어지는 수에서 +1 값이 출력되는 문제였음. 기본값을 N, NN, NNN... 으로 채울 때 number와 비교하는 걸 한 번 넣어줘서 해결.