프로그래머스 : N으로 표현

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

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

 

N은 8번까지만 사용하면 됩니다. 그 이상은 -1을 반환해주면 됩니다.

만약 N이 3이라면,

1번 사용하는 경우 -> 3

2번 사용하는 경우 -> 33

3번 사용하는 경우 -> 333

4번 사용하는 경우 -> 3333

5번 사용하는 경우 -> 33333

6번 사용하는 경우 -> 333333

7번 사용하는 경우 -> 3333333

8번 사용하는 경우 -> 33333333

위와 같이 8개의 경우로 나누어서 저장해줍니다.

​

N을 2번 사용하는 경우 -> ((N을 1번 사용하는 경우) (+-*/) (N을 1번 사용하는 경우))

N을 3번 사용하는 경우 -> ((N을 1번 사용하는 경우) (+-*/) (N을 2번 사용하는 경우))

((N을 2번 사용하는 경우) (+-*/) (N을 1번 사용하는 경우))

N을 4번 사용하는 경우 -> ((N을 1번 사용하는 경우) (+-*/) (N을 3번 사용하는 경우))

((N을 2번 사용하는 경우) (+-*/) (N을 2번 사용하는 경우))

((N을 3번 사용하는 경우) (+-*/) (N을 1번 사용하는 경우))

... 처럼 될 것입니다.

​

dp[i]는 N을 i번 사용하는 경우의 수 집합이라고 하면,

dp[i] = { dp[1] (+-*/) dp[i -1],

dp[2] (+-*/) dp[i -2],

dp[3] (+-*/) dp[i -3], .... } 입니다.

#include <string>
#include <vector>
using namespace std;

int cal(int a, int b, int t) {
    if(t == 0) return a + b;
    else if(t == 1) return a - b;
    else if(t == 2) return a * b;
    else {
        if(b > 0) return a / b;
    }
    return -1;
}

int solution(int N, int number) {
    if(N==number) return 1;
    vector<int> dp[8];
    dp[0].push_back(N);
    for(int i=1; i<8; i++) {
        int val = dp[i-1][0]*10 + N;
        if(val == number) return i+1;
        dp[i].push_back(val);
    }
    
    for(int i=1; i<8; i++)
        for(int j=0; j<=i-1; j++)
            for(int k=0; k<dp[j].size(); k++)
                for(int l=0; l<dp[i-1-j].size(); l++)
                    for(int m=0; m<4; m++) {
                        int val;
                        if((val = cal(dp[j][k], dp[i-1-j][l], m)) == number) return i+1;
                        if(val != -1) dp[i].push_back(val);
                    }

    return -1;
}