프로그래머스 - N으로 표현 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

 

정말 수준높은 DP문제라고 생각한다. 동적계획법은 언제나 어렵고 나를 힘들게한다..

 

먼저 이 문제 분류를 통해 동적계획법을 알고 들어가긴 했지만 DP를 써야하는 이유는 역시나 이전의 값을 다시 재사용하게 된다는 점이다.

 

처음 접근할 때 DP[1]~ DP[32001] 를 각 N이 만들 수 있는 점화식을 구하여 보려 했으나 44퍼센트에서 틀렸다.. 아주 어림없는 도전은 아니었다고 생각하는데 아쉽다.

 

이 문제는 다른 DP들은 그저 최적의 값을 저장해둘 뿐인데 DP에 값을 여러개 저장해놓는 방식을 사용하게 된다.

 

예를들어 예제처럼 5를 사용한다고 할 때 사용하는 5의 개수를 인덱스로 한다고 생각해보자.

 

dp[1] = 5

dp[2] = 55, 5 + 5, 5 - 5, 5 / 5, 5 * 5

dp[3] = 555, 5 + 5 + 5, 5 + 5 - 5, (5 + 5) * 5, (5 + 5) / 5 , 5 - 5 + 5 , ...

 

규칙이 만들어졌다. dp[i]는 dp[i - 1]과 dp[i - 2]의 모든 사칙연산 + 5의 i자리수 표현을 만들어낼 수 있다.. 라고 생각하면 큰 오산이다! 

 

dp[4]의 경우는 dp[3]과 dp[1]의 연산으로 만들어진다. 즉,

 

k개의 N을 사용하여 만들어낼 수 있는 숫자들 = i개로 만들어 낼 수 있는 숫자들과 j개로 만들어 낼 수 있는 숫자들의 사칙연산

 

이걸 알아채야하는데 정말 쉽지않다... 레벨4가 맞는 것 같다. 그러므로 첫 시작인 dp[1], dp[1]끼리 시작하며 Bottom Up 방식으로 DP를 갱신해간다. 이 때 흥미롭게 DP에는 값들이 들어간다. 그리고 이 값들은 중복이 들어갈 필요가 없다. 그래서 SET을 사용한다.

 

DP[i] => i개의 N을 사용하여 만들어 낼 수 있는 숫자들의 집합

 

이 되는 것이다. 

 

그리고 이 문제의 N의 조건은 모두 양수이기 때문에 음수는 필요없다. 만약 음수가 들어가게되면 연산을 하며 0이만들어져 0으로 나누기가 될 수도 있다. 그래서 0과 음수는 제외하고 셋에 넣도록 한다.

다시봐야할 어려운 문제이다.

 

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

set<int> dp[9];
int getN(int n, int idx){
    int result = 0;
    while(idx){
        result += n;
        n *= 10;
        idx--;
    }
    
    return result;
}
int solution(int N, int number) {
    int answer = 0;
    
    for(int t = 1; t < 9; t++){
        dp[t].insert(getN(N, t));
        
        for(int i = 1; i < 9; i++){
            for(int j = 1; j < 9; j++){
                if(i + j != t) continue;
                
                for(int a : dp[i]){
                    for(int b : dp[j]){
                        dp[t].insert(a + b);
                        if(a > b)
                            dp[t].insert(a - b);
                        dp[t].insert(a * b);
                        if(a / b > 0)
                            dp[t].insert(a / b);
                    }
                }
            }
        }
        
        if(dp[t].find(number) != dp[t].end()){
            return t;
        }
    }    
    return -1;
}