[프로그래머스/c++] N으로 표현

문제

숫자 N을 사칙연산을 통해 number로 표현할 때 사용되는 N의 최소 사용횟수를 구한다.

---

접근

• 규칙을 찾아서 dp 배열을 만들어 적용시키고자 하였으나 무엇을 기준으로 규칙을 찾아야 할 지 감이 잡히지 않아 문제에서 구하고자 하는 것을 다시 살펴보았다.
• N의 최소 사용횟수를 구한다는 점에서, N을 1개, 2개, 3개 ... 사용해서 만들 수 있는 수들을 직접 적어보았다.
• 다음 예시를 통해 살펴보자.

N	number	return
2	11	3

 

dp[cnt]: N을 cnt 개수 만큼 사용하여 만들 수 있는 수
dp[1]	- 2
dp[2]	- 22 dp[1]과 dp[1]로 사칙연산 - 2+2=4 - 2-2=0 - 2*2=4 - 2/2=1
dp[3]	- 222 dp[1]과 dp[2]로 사칙연산 - 2와 22로 사칙연산 - 2와 4로 사칙연산 - 2와 0으로 사칙연산 - 2와 4로 사칙연산 - 2와 1로 사칙연산 dp[2]와 dp[1]로 사칙연산 - 22와 2로 사칙연산 -> 여기서 22/2로 11이 나온다. 따라서 2를 3개 사용하여 11을 만들 수 있다!! - 4와 2로 사칙연산 - 0과 2로 사칙연산 - 4와 2로 사칙연산 - 1과 2로 사칙연산

😀

이를 일반화 해보면

dp[n]은

dp[1]과 dp[n-1]간 사칙연산 + dp[2]과 dp[n-2]간 사칙연산 + dp[3]과 dp[n-3]간 사칙연산 + ... + dp[n-1]과 dp[1]간 사칙연산을 통해 구할 수 있다!

---

성공 코드(내 코드)

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

using namespace std;

int solution(int N, int number) {
    int answer = -1, n_cnt=1;
    vector<vector<int>> dp(9);
    for(int i=1; i<9; i++){
        int sum=0;
        for(int j=1; j<=i; j++){
            sum+=N*pow(10, j-1);
        }
        dp[i].push_back(sum);
        if(sum==number) return i;
    }
    for(int i=2; i<9; i++){
        for(int j=1; j<i; j++){
            for(int k=0; k<dp[j].size(); k++){
                for(int h=0; h<dp[i-j].size(); h++){
                    dp[i].push_back(dp[j][k]+dp[i-j][h]);
                    dp[i].push_back(dp[j][k]-dp[i-j][h]);
                    dp[i].push_back(dp[j][k]*dp[i-j][h]);
                    if(dp[i-j][h]!=0){
                        dp[i].push_back(dp[j][k]/dp[i-j][h]);
                        if(dp[j][k]/dp[i-j][h]==number) return i;
                    }
                    if(dp[j][k]+dp[i-j][h]==number ||
                       dp[j][k]-dp[i-j][h]==number ||
                       dp[j][k]*dp[i-j][h]==number) return i;
                }
            }
        }
    }
    
    return answer;
}

 

---

후기

DP 연습을 위해 풀게된 문제인데, 해당 문제는 Level3으로 측정되어 있었으나 개인적으로 다른 Level3의 문제보다 어렵게 느껴졌다. 생각보다 반복문도 많이 들어가서 구현할 때 이게 맞나 싶기도 했는데 맞다고 떠서 다행이었다 ㅎㅎㅎ...