프로그래머스 [level3] N으로 표현 (Dynamic Programming)

문제

 

 

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(int N, int number) 
{
    int answer = 0;
    
    vector<vector<int>> m_vecDp(9); 
    
    int sum =0; 

    for(int i=1; i<=8; i++)
    {
        sum = 10*sum + N; 
        m_vecDp[i].push_back(sum);
    }
    
    for(int i=2; i<=8; i++)
    {
        for(int k=1; k<i; k++)
        {
            int j= i-k;
                
            for(auto& iter_k : m_vecDp[k])
            {
                for(auto& iter_j : m_vecDp[j])
                {
                    m_vecDp[i].push_back(iter_k + iter_j);
                    m_vecDp[i].push_back(iter_k - iter_j);
                    m_vecDp[i].push_back(iter_k * iter_j);
                    if (iter_j != 0)
                        m_vecDp[i].push_back(iter_k / iter_j);
                }   
            }
              
         }
     }
    
    for(int i=1; i<=8; i++)
    {
        for(auto& iter : m_vecDp[i])
            {
                if(iter == number)
                {
                    answer = i;
                    return answer; 
                }
            }
    }
    
    answer = -1; 
    
    
    
    return answer;
}

 

 

 

 

 문제 접근 순서 

 

1. 처음에는 아무리 생각해도 규칙성을 어떻게 짜야하고 어디까지를 제한을 둬서 반복문을 돌려야 할지 너무 막막했다. 

 

2. 문제를 자세히 보니 최솟값이 8보다 크면 -1을 return 하라고 나와 있는걸 보고 눈치를 채서 

   아 for문을 8이하 까지 돌려라는 말이구나를 눈치 챘다. 

 

3. 하지만 문제의 규칙성을 이해하지 못하여 하나하나 대입해가면서 점화식을 세워봣다.   

Dp[1] =  5 (// 여기서 "1"은 5가 1개 쓰인 것 이라는 의미)  

Dp[2] = (Dp[1] ,DP[1]) , 55  

Dp[3] = (Dp[1], Dp[2]), (Dp[2], Dp[1]) 

 여기서 부터 눈치 챘다. 아  Dp[i] = D[k] + D[j] (i= k+j) 이라는 점화식이 라는 것을 

 

4. 따라서 이제 규칙성을 찾았으니 해당 식을 코드로 작성하였다.

   (주의할 점으로는 "0" 나누기 와 범위 관련 표현이였다.)  

 

5. set으로 중복을 제거하는 편이 효율적이였을것같다 ( vector<vector<int>> 를 vector<set<int>> 로 )