[DP] N으로 표현

문제

 

 

접근법

 

- 주어진 숫자 N을 최소한의 횟수로 조합하여 number를 만들어야 하기 때문에, 최적 부분 구조와 중복되는 부분문제가 존재한다. 따라서 DP가 적합하다.

 

* 최적 부분 구조란?

 - 중복되는 부분문제의 해결을 통해 문제의 해를 도출해 낼 수 있는 구조를 의미함.

 

* 중복되는 부분 문제란?

 - 최적의 해를 찾기 위해서 반복되는 부분 문제가 존재할시, 해당 문제를 의미함.

 

* 문제에서 얻을 수 있는 힌트

 

1. 사칙 연산만 가능 -> 단순한 연산 조합을 반복하여 만들 수 있음
2. 최소 횟수를 구하는 문제 -> BFS 나 DP가 적합
3. N을 여러번 조합하여 만들 수 있음 -> 작은 문제의 결과를 조합해 나갈 수 있음 -> DP 적용 가능.

 

* 풀이 방법

 

DP 배열 dp[i]는 N을 정확히 i번 사용하여 만들 수 있는 모든 수의 집합이다.

 

1. 초기화

• dp[1] = {N};
• dp[2] = {NN, N+N,N-N,N*N,N/N};

2. 점화식 적용

• dp[k]를 만들때, dp[a]와 dp[b]를 조합해서 생성 (a+b =k)
• 예를들어 dp[3] = {dp[1]+dp[2], dp[2]+dp[1]};

3. 종료조건

• dp[i]에 number 가 포함되면 i를 반환
• 8번을 초과하면 -1 반환

 

코드

 

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int solution(int N, int number)
{
    vector<set<int>> dp(9);

    int n=0;
    for(int i=1;i<9;i++)
    {
        n=n*10+N;
        dp[i].insert(n);
    }


    for(int i=1;i<9;i++)
    {
        //dp[1]~dp[8] 계산
        //dp[n] = dp[1]dp[n-1]+ .. +dp[n-1]dp[1]
        for(int j=1;j<i;j++)
        {
            for(auto a : dp[j])
            {
                for(auto b : dp[i-j])
                {
                    dp[i].insert(a+b);
                    dp[i].insert(a-b);
                    dp[i].insert(a*b);
                    if(b!=0) dp[i].insert(a/b);
                }
            }
        }

        if(dp[i].find(number)!=dp[i].end())
        {
            return i;
        }
    }
    return -1;
}