[프로그래머스] N으로 표현 - C++

문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

 

---

DP를 사용한 문제

 

🔗 참고 : N으로 표현

 

문제를 어떻게 쪼개야 할지 몰라서 접근도 못하고 있다가 힌트를 얻고 풀었다.

 

N의 사용 횟수를 보면

N = 1일때 DP[1] = 1

N = 2일때 DP[1]을 가지고 사칙연산을 수행(N + N, N - N, N * N, N / N)하는 4가지에 두 수를 연달아 붙인 NN까지 포함하여 DP[2] = 5

N = 3일때 DP[1]과 DP[2]로 사칙연산을 수행하는 경우의 수, DP[2]와 DP[1]로 사칙연산을 수행하는 경우의 수, NNN

...

이런식으로

 

횟수가 i번일 때의 경우의 수는 DP[1] & DP[i - 1], DP[2] & DP[i - 2], ... , DP[i - 1] & DP[i] 와의 사칙연산을 수행하였을 때의 경우의 수에 N을 i번 사용한 경우를 더하면 규칙을 찾을 수 있다.

 

코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int N, int number) {
    if(N == number) return 1;

    vector<vector<int>> dp;
    dp.push_back({ 0 });
    dp.push_back({ N });
    
    for(int i = 2; i <= 8; i++) {
        vector<int> temp;

        int k = 0, calc = 0;
        while(k != i) {
            calc += N * (int)pow(10, k++);
        }
        temp.push_back(calc);

        for(int j = 1; j < i; j++) {
            for(int l = 0; l < dp[j].size(); l++) {
                for(int m = 0; m < dp[i - j].size(); m++) {
                    if(dp[i - j][m] == 0) continue;
                    temp.push_back(dp[j][l] + dp[i - j][m]);
                    temp.push_back(dp[j][l] - dp[i - j][m]);
                    temp.push_back(dp[j][l] * dp[i - j][m]);
                    temp.push_back(dp[j][l] / dp[i - j][m]);
                }
            }
        }

        for(int j = 0; j < temp.size(); j++) {
            if(temp[j] == number) return i;
        }

        dp.push_back(temp);
    }

    return -1;
}