프로그래머스 : N으로 표현 JavaScript

var min = 9;

function DFS(N, number, count, result) {
    if(min <= count) return;

    if(result===number) {
        min = min > count ? count : min;
        return;
    }

    if(count===8) return;

    let rest = 8 - count;
    let nn = 0;
    for(let i=0;i<rest;i++){
        nn = nn * 10 + N;
        DFS(N, number, count+1+i, result+nn);
        DFS(N, number, count+1+i, result-nn);
        DFS(N, number, count+1+i, result*nn);
        DFS(N, number, count+1+i, result/nn);
    }

}

function solution(N, number) {
    
    var answer = 0;
    DFS(N, number, 0, 0);
    if(min> 8)
        answer = -1;
    else
        answer = min;

    return answer;
}

N 1개로 만들 수 있는 표현  : N

N 2개로 만들 수 있는 표현 : N+N , N/N, NN, N*N, N-N

N 3개로 만들 수 있는 표현 : N+N+N, NN/N, NNN, NN*N, NN-N, N-NN

 

가장 중요한건 연속된 NN이다. DFS로 모든 사칙연산에 대해서 조사한다면 완전탐색가능하다.

 

( N3회 사용) (사칙연산) DFS(1~5회사용) 이런식으로 로직을 짜서 전수탐색가능.