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

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

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

 

 

dp[i]에 무엇을 저장할지 dp핵심을 다시 생각해보고 그에 맞는 자료구조를 떠올릴 수 있어야 풀 수 있는 아주 좋은 문제였던 것 같다.

 

dp란 다음 가정을 만족할 때 적용하는 알고리즘

1. 큰 문제를 작은 문제로 나눌 수 있다

2. 작은 문제에서 산출된 결과를 큰 문제에서 활용할 수 있다.

 

그리고 이에 따라 문제에서 dp[i]의 i로 기준 잡을 수 있는 요소를 생각해내야한다.

 

이 문제에서는 dp[i]란 N을 i번 사용해서 만들 수 있는 수들의 집합

즉 dp[i]는 또 하나의 배열이며, 중복을 허용하지 않는 자료구조 set을 이용해야한다는 것까지 도출해내야한다.

 

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int condN(int N, int cnt){
    int newN = N;
    for(int i=1; i<cnt; i++){
        newN *= 10;
        newN += N;
    }
    return newN;
}

int solution(int N, int number) {
    if(N == number) return 1;
    
    int answer = 0;
    
    vector<unordered_set<int>> v(9);
    
    v[1].insert(N);
    
    for(int i=2; i<=8; i++){
        v[i].insert(condN(N, i));
        
        for(int j=1; j<=i; j++){
            for(int k=1; k<=i; k++){
                if(j+k>8) break;
                
                for(auto a : v[j]){
                    for(auto b : v[k]){
                        v[j+k].insert(a+b);
                        v[j+k].insert(a*b);
                        if(a-b>0) v[j+k].insert(a-b);
                        if(b!=0) v[j+k].insert(a/b);
                    }
                }
            }
        }
        if(v[i].find(number) != v[i].end())
            return i;
    }
    
    return -1;
}