[프로그래머스] 동적계획법 (Dynamic Programming) N으로 표현

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

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

 

처음에 보고 익숙하긴 했는데, 이런 문제는 DFS 로 풀었던지라 왜 DP 로 풀란건지 싶었다.

얼추 숫자 횟수를 기준으로 잡으면 되겠다라고 생각했다.  

 

1. DP 에 N 사용횟수를 인덱스로 잡고

2. 만들 수 있는 숫자들을 집어 넣는다.

- x개를 사용해서 만들수 잇는 수를 구하는 방법은

1) NNNN....NN : x번 그냥 숫자만 이용

2) k는 1~k-1 까지

- dp[x-k] + dp[k]

- dp[x-k] * dp[k]

- dp[x-k] - dp[k]

- dp[x-k] / dp[k]

- 주의해야 할점은 나누기 할때 수를 0 으로 나누지 않도록 if 하나 걸어주기

3. 집어넣은 수 중에 number가 있는지 확인하고 있다면 현재 인덱스를 리턴해준다. 

4. 인덱스가 8 보다 커지면 -1 로 리턴한다.

 

조금 해맸던 점은, 제곱을 할때 식을 pow(10, i) 가 아닌 10*i 로 잘못 작성해놓고 잘못된거 찾지못해서 8번 통과 안된다고 삽질했다.

이런식의 dp 도 있구나 싶었다.

 

[전체 코드]

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>

using namespace std;


int solution(int N, int number) {
    int answer = 0;
    
    if(N == number)
        return 1;
    
    vector <vector<int>> v(9);
    
    v[1].push_back(N);  
    
    int start = 2;
    while(start <= 8) {
        
        int tmp = N;
        for(int i=1; i<start; i++)
            tmp += N * pow(10, i);

        v[start].push_back(tmp);
        
        for(int i=1; i<start; i++) {
            vector <int> a = v[i];
            vector <int> b = v[start-i];
            
            for(auto ele1 : a) {
                for(auto ele2 : b) {
                       
                    v[start].push_back(ele1+ele2);
                    v[start].push_back(ele1*ele2);
                    
                    v[start].push_back(ele1-ele2);
                    
                    if(ele2 != 0 && ele1/ele2 > 0)
                        v[start].push_back(ele1/ele2);
                }
            }
        }
        for(auto ele: v[start]) {
            if(ele == number)
                return start;
        }  
        
        start++;
    }
    
    return -1;
}