[프로그래머스/Level 3] N으로 표현 (C++)

programmers.co.kr/learn/courses/30/lessons/42895

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

DP 유형의 문제이지만 DFS를 이용한 완전탐색으로 해결한 문제

+N, -N, *N, /N

+NN, -NN, *NN, /NN

+NNN, -NN, *NN, /NN

....

반복적인 작업을 통해 만약 N을 사용한 갯수(cnt)가 9이상이라면 가지를 뻗지 않고 리턴, 위의 작업을 하며 만들어진 수(sum)이 number와 같다면 최소값을 갱신해줍니다.

 

#include <string>
#include <vector>

using namespace std;

int answer = 9, N, Number;

void DFS(int now, int cnt) {
    if(cnt >= 9) return;
    if(now == Number) {
        answer = min(answer, cnt);
        return;
    }
    
    int tmp = 0;
    for(int i = 0; i < 8; i++) {
        tmp = 10 * tmp + N; // 5, 55, 555, 5555 ...
        DFS(now + tmp, cnt + 1 + i);
        DFS(now - tmp, cnt + 1 + i);
        if(now != 0) {
            DFS(now * tmp, cnt + 1 + i);
            DFS(now / tmp, cnt + 1 + i);
        }
    }
}

int solution(int n, int number) {
    N = n;
    Number = number;
    DFS(0, 0);
    if(answer == 9) return -1;
    return answer;
}