[프로그래머스] 레벨 3 - N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895?language=cpp

코딩테스트 연습 - N으로 표현 | 프로그래머스

DFS 완전탐색으로 풀 수 있는 문제다.

깊이가 최대 8이므로 충분히 시간 내에 탐색할 수 있다.

특이한 점은 19행 ~ 29행으로 5, 55, 555, 5555와 같은 수를 더하거나 빼거나 곱하거나 나눌 수 있다는 것이다.

이 때 해당하는 숫자 만큼 dfs count변수에 더해줘야 한다.

 

어느 dfs 문제와 동일하게 백트래킹에도 신경을 잘 써줘야 한다.

기본적으로 깊이 초과시 리턴, 답을 찾을 시 리턴하는 것과 더불어 0에 곱하거나 나누는 것을 하지 않도록 25,26행에 설정해주는 것이 필요하다.

 

DFS 레벨 3 문제.

#include <string>
#include <vector>
#include <algorithm>
#define MAX 987654321
using namespace std;
int answer = MAX;
int globe_N, globe_tnum;
 
void dfs(int count, int sum){
    if(count > 8){
        return;
    }
    
    else if(count <= 8 && sum == globe_tnum){
        answer = min(answer, count);
        return;
    }
    
    int n=0;
    for(int i=0; i<8; i++){
        n = n * 10 + globe_N;
        dfs(count+i+1, sum+n);
        dfs(count+i+1, sum-n);
        if(sum != 0){
            dfs(count+i+1, sum*n);
            dfs(count+i+1, sum/n);
        }
    }
}
 
int solution(int N, int number) {
    globe_N = N, globe_tnum = number;
    dfs(0, 0);
    return ( answer == MAX ) ? -1 : answer;
}