[Programmers][C++] N으로 표현 ( level 3)

[문제보기]

 Programmers. N으로 표현

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

[풀이과정]

 (1) dfs(int cnt, int num)

      cnt에는 현재 N이 들어간 개수를 카운트해주는 변수이다. 이 cnt가 MAX(=9)와 같거나 커지게 되면,

      그냥 return을 해준다. (문제에서 N이 8개가 넘어가면 -1로 출력하라는 말이 있다)

      두 번째 if문에서 num과 입력값으로 주었던, number의 값이 같은지 확인 후 같으면 ans와 cnt를 비교,

      더 작은 값을 ans에 업데이트시켜준다. 

      for문을 돌면서 num에 사칙연산(+, -, *, /)을 해준다. 이때, num에는 N, NN, NNN, NNNN..., 형식으로

      num에 사칙연산을 하고, cnt에는 N의 들어간 개수+1을 더해주고 재귀 함수를 수행해준다.

  

      * for문을 돌면서 N, NN, NNN, NNNN...을 해주는 이유는 모든 경우의 수에 대해 다 해보고 최솟값을 찾기

        위함이다. 그리고 *, / 의 경우 num가 0이 아닐 경우에만 수행을 하는데, 0에 곱하거나 나누기를 하는 경우 0이 

        되기 때문이다.

 

 (2) solution(int n, int number)

       다른 함수에도 n과 number의 데이터를 사용하기 위해 전역 변수 num_glb, n_glb에 각 데이터를 넣어준다.

       dfs를 수행하고, 만약 ans가 MAX값이면, 8보다 작은 최솟값을 찾기 못한 것이므로 ans에 -1을 반환해준다. 

[소스코드]

#include <string>
#include <vector>
#define MAX 9
using namespace std;
int ans = MAX, num_glb, n_glb;

void dfs(int cnt, int num){
    if(cnt >= MAX)
        return;
    
    if(num == num_glb){
        if(ans > cnt)
            ans = cnt;
        return;
    }
    
    int n = 0;
    for(int i=0; i<8; i++){
        n = (n*10) + n_glb;
        dfs(cnt+i+1, num+n);
        dfs(cnt+i+1, num-n);
        if(num != 0){
            dfs(cnt+i+1, num*n);
            dfs(cnt+i+1, num/n);
        }
    }
}

int solution(int N, int number) {
    num_glb = number;
    n_glb = N;
    dfs(0, 0);
    if(ans == MAX)
        ans = -1;
    return ans;
}

int main(){
}

 

[해결 과정중 실수한 부분]

 

 

---