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

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

using namespace std;

int make_NN(int N, int counts);

int solution(int N, int number) {
    if(N == number) return 1;
    
    vector<unordered_set<int>> dp(9);
    dp[1].insert(N);
    
    for(int i = 2; i <= 8; i++)
    {
        for(int x = 0; x < i; x++)
        {
            for(int y = 0; y < i; y++)
            {
                for(auto a : dp[x])
                {
                    for(auto b : dp[y])
                    {
                        if (x + y != i) continue;   //현재 횟수만큼만 사용하기 위함 3번 사용일경우 2.2같은 경우방지
                        
                        dp[i].insert(a + b);
                        dp[i].insert(a * b);
                        
                        if(a - b > 0)
                            dp[i].insert(a - b);
                        if(a / b > 0)
                            dp[i].insert(a / b);
                        
                    }
                }
            }//for(int y = 0; y < i; y++)
        }
        
        dp[i].insert(make_NN(N, i));
        
        if (dp[i].count(number))
            return i;
    }
    
    return -1;
}

int make_NN(int N, int counts)
{
    int result = N;
    for(int i = 1; i < counts; i++)
        result = result * 10 + N;
    
    return result;
}

풀이

1. nn, +, -, *, /가 있다

2. 주어지는 N은 1~9이다

3. 최소값이 8보다 크면 -1로 return이므로 8번횟수까지만 계산

4. 계산은 dp1, ( dp1 + dp1, dp1 - dp1 ..., NN), (dp1 + dp2 ... NNN)으로 된다.

5. 해당 N의 사용횟수만큼 저장한 값dp를 다 계산해준다. 3번째의 경우 dp1의 값들과 dp2에 있는 것을 계산

6. 해당 횟수에 number가 있을 경우 해당 횟수를 return 해준다.

 

 

 

 

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

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