[C++] 프로그래머스 'N으로 표현' 풀이

문제 설명

아래와 같이 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 합니다.

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int solution(int N, int number) {
    int answer = 0;
    vector<set<int>> dp(9); //insert 쓰려면 크기 미리 지정해야함 
    for(int i=1;i<9;i++){
        int tmp=0;
        for(int j=0;j<i;j++) tmp=tmp*10+N; //N이 여러개 나오는 거 저장 
        dp[i].insert(tmp); //tmp는 N i개 쓰임 
        
        for(int j=1;j<i;j++){
            int left=j;
            int rigt=i-j;
            //i랑 j랑 쪼개어서 
            for(int x: dp[left]){
                for(int y:dp[rigt]){
                    dp[i].insert(x+y);
                    dp[i].insert(x-y);
                    dp[i].insert(x*y);
                    if(y!=0 && x%y==0) dp[i].insert(x/y);
                    //사칙연산의 값은 i번째에 나옴 
                }
            }
        }
        
        if(dp[i].count(number)) return i; //number가 있다면 우리가 0부터 점증적으로 검사중이니 지금이 최소값 
    }
    
    return -1;
}

 

DP는 처음인데 풀다가 지피티 도움 받았다.. 

으음.. 테이블을 잘 선정하기 위해서 생각을 좀 해봐야할 거 같다.