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

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

프로그래머스

 

생각의 과정

 

1. dfs를 이용한 완전탐색으로 하려고 했다 

2. 괄호를 처리하려니 너무 복잡함

3. 괄호 처리가 필요 없다

왜나하면 모든 경우를 다 훑기 때문에 괄호를 사용한 경우와 사용하지 않은 경우를 다 확인하기 때문에

예를 들어 

55+5/5의 경우

5/5 + 55 를 탐색할 때 찾게 됨

 

#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <math.h>
#include <stack>
#include <queue>
#include <sstream>

using namespace std;

int target, NUM;

int go(int cnt, int val)
{
    if(cnt > 8)
        return 2e9;
    if(val == target)
        return cnt;
    
    int ret = 2e9;
    int n = 0;
    for(int i = 1; i <= 8; i++){
        n = 10*n + NUM;
        ret = min(ret, go(cnt+i, val + n));
        ret = min(ret, go(cnt+i, val - n));
        ret = min(ret, go(cnt+i, val * n));
        ret = min(ret, go(cnt+i, val / n));
    }
    
    return ret;
}

int solution(int N, int number) {
    int answer = 0;
    target = number;
    NUM = N;
    
    answer = go(0, 0);
    if (answer == 2e9)
        answer = -1;
    return answer;
}