N으로 표현(DP) / C++

1. 문제

2. 접근 방법

1) 문제 조건, 제한 범위 찾기 

   - N은 최대 8번 사용 가능하다 => 연산을 수행할 수는 N~NNNNNNNN까지 가능

   - 괄호 사용 가능

2) DFS로 풀기

   2-1) 종료 조건 : 원하는 수를 찾았을 때, cnt가 8을 넘어갔을 때

   2-2) 재귀 함수 호출 : 0부터 시작, 현재 수에 N부터 NNNNNN까지 사칙 연산을 각각 수행하면서 재귀함수를 호출한다. => 현재 수 (+ / - / * / 나눗셈) N,NN,NNN,...,NNNNNN

 

   2-3) 효율적으로 짜는 법 :

• - 현재 수가 0인 경우엔 곱셈 나눗셈 수행 안함

• - 2-2)에서 현재 수에 연산할 N의 범위는 최대 NNNNNN이다. (for문은 N부터 NNNNNN까지 6번 수행)

    NNNNNNN과 NNNNNNNN이 안되는 이유?    

 * 만약 현재 수에 연산할 수가 NNNNNNN(N이 8개)이 나오려면 현재 수는 0이어야 한다 => 0과 연산을 수행한 결과는 (0 + NNNNNNNN)과 (0 - NNNNNNNN). => 해당 값들로 다시 재귀 호출하면, cnt가 8이므로 더 이상 연산 불가 & number는 최대 5자리 수 이므로 NNNNNNNN이나 -NNNNNNNN이 될 수 없음 => return당함

 

 * 만약 현재 수에 연산할 수가 NNNNNNN(N이 7개)가 나오려면 현재 수는 0이거나 N이어야 한다.

( 현재 수가 0일 때 ) 0과 NNNNNNN을 연산을 수행한 결과인 (NNNNNNN, -NNNNNNN)로 재귀 호출 => 다시 사칙 연산을 수행하려고 보니까 cnt = 7이므로 사칙 연산 할 수 있는 수는 N만 가능 => 연산 결과는 반드시 최소 7자리 수 이상이다(NNNNNNN + N, NNNNNNN -N, NNNNNNN *N, NNNNNNN / N) => 해당 값들로 재귀 호출해도 cnt == 8이므로 더 이상 연산 불가 & number는 최대 5자리 수 이므로 일치하지 않음 => return 당함 

 

( 현재 수가 N일때 ) N과 NNNNNNN을 연산 한 결과 값으로 재귀 호출하면, cnt가 8이므로 더 이상 연산 불가 & 연산 결과 값은 항상 7자리수 이상이다. 마찬가지로 numbers는 최대 5자리 수이므로 될 수 없음 => return

 

3) DP로 풀기(bottom- up)

  3-1) DP배열 정하기 : (vector<int>) dp[i]: N을 i번 사용해서 만들 수 있는 수들의 집합 

  3-2) DP배열 초기값 : dp[i]에 각각 NN...N(i개)를 저장

  3-3) 배열에 값 업데이트 : https://gurumee92.tistory.com/164 참고함

프로그래머스 문제 풀이 N으로 표현

  - dp[i] : N을 i번 사용하여 만들 수 있는 수들의 집합 = ( dp[1] 연산 dp[i-1] ) U (dp[2] 연산 dp[i-2] ) ... U (dp[7] 연산 dp[1]) 

  - 왜 for문의 범위를 0~8까지 했는지? : 괄호 처리를 위해!!(ex. dp (55+5) / 5 와 같이 덧셈이나 뺄셈을 먼저 수행하는 경우의 수도 만들기 위해) 

  -  주의할 범위 : 0으로 나누는 경우 발생하지 않도록 함 

 

3. 조심할 것 & 배운 점

1) 문제에는 DP라고 써있는데 만약 모의고사로 나왔으면 난 DFS로 풀었을 것 같다. 

 

2) DP 배열 정의 부분에서 오래걸렸다. 처음에 dp[number]를 number을 만들기 위한 N의 최소 사용 횟수 라고 정했는데, 그렇게 하면 dp[N-i]와 dp[N]의 관계식을 구하기 어려웠다. 물론 좀 더 생각한다면 방법이 있겠지만 아직 쪼랩인 나에겐 넘나 힘든 과정이므로, 답이 안나올 것 같으면 과감히 포기하고 다른 발상을 생각해보자. 

=> dp배열에서 중요한 것이 "배열index의 의미"와 "배열에 들어있는 값"인데, 둘을 바꿔서 접근하는 연습도 하자.

 

3)  set을 써야 중복이 방지 된다! (set 쓰는 연습 하기)

 

4) dfs로 풀 때 처음 시작 값을 NNN혹은 NN 등 number의 자리수 만큼 시작했는데, 왜 굳이 0부터 시작하는 걸까? => 어차피 모든 경우를 다 돌아야 함(브루트 포스)

왜 중간 값부터 시작하면 안되는 걸까? : 최소값을 구해야 하므로 결국 모든 경우의 수를 알아내야 한다. 따라서 시작 부분은 크게 고려하지 않아도 된다.

 

5) 0에서 곱하기 나눗셈 경우를 제거해야 함

 

6)core dump 발생 시, for문의 범위를 바꿔가면서 확인 해볼 것

 

7) 기초적인 실수를 했다. tmp = tmp*10 + N해야 tmp값이 갱신되는데 tmp*10 +N값으로 dp에 넣어서 tmp값이 업데이트가 안되었다..(코드 참고)

 

8) 효율성은 DP가 더 좋은 것 같다. DP로도 풀 수 있도록 실력을 쌓쟈..

4. 코드

1) DFS

#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 8
using namespace std;

int gloN, res = MAX + 1;
void dfs(int number, int curNum, int cnt) {
    if( cnt > MAX ) return;
    else if( curNum == number ){
        res = min(res, cnt);
        return;
    }
    int n = 0;
    for(int i = 1;i<= 6;i++) {
        n = n*10 + gloN; 
        dfs(number, curNum + n, cnt + i);
        dfs(number, curNum - n, cnt + i);
       if(curNum != 0) {
        dfs(number, curNum * n, cnt + i);
        dfs(number, curNum / n, cnt + i);
       }
    }
}

int solution(int N, int number) {
    gloN = N;
    dfs(number,0,0);
    return (res == 9) ? -1 : res;
}

2) DP

#include <set>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(int N, int number) {
    set<int> dp[9];
    int tmp = 0;
    for(int i= 1; i<= 8; i++){ 
       tmp = tmp*10 + N;
        dp[i].insert(tmp);
    }

    for(int i = 1;i<= 8; i++) {
        for(int j = 1;j<=i; j++) {
            for( auto x : dp[j]) {
                for (auto y : dp[i-j]) {
                    dp[i].insert(x + y);
                    dp[i].insert(x - y);
                    if( x!= 0 && y != 0) {
                     dp[i].insert(x * y);
                     dp[i].insert(x / y);
                    }
                }
            }
        }
        if(dp[i].find(number) != dp[i].end() ) return i;
    }
    return -1;
}