programmers N으로 표현

programmers : https://programmers.co.kr/learn/courses/30/parts/12263

 

programmers DP(동적계획법) level3 N으로 표현 문제입니다.

 

원래 dp 문제를 풀때 최적화되는 과정을 생각해보고

최적화를 위한 코드를 짜는게 맞긴한데

 

이 문제는 dp문제지만 어떤식으로 최적화를 해야되는건지 솔직히 모르겠다.

그래서 평소 dp문제를 풀 때 처럼 재귀로 문제를 풀었지만, 최적화..는 하지 못했다.

 

만약 dp를 제대로 풀기 위한 최적화방법을 고려해본다면..

N으로 만들 수 있는 모든 수 N,NN,NNN,NNNN,... 을 미리 8자리까지 만들어놓고

음.. dp[a][b] 의 2차원형태로 접근해본다면

a는 위에 미리 만들어놓은 값들, b는 만들어낼 수 있는 값들 (0~?????)

dp[a][b] 는 cnt 가 되겠다.

 

사실 문제풀때는 N을 8번 사용하라는 얘기 때문에 반복문을 8까지 돌렸는데

생각해보면 표현할 범위의 최대가 32000 이기 때문에

아무리 큰 숫자를 만든다고 해도 32000을 9로 곱한 수 인 288000 가 확인해볼 최댓값이 되겠다.

결국 8까지 돌려볼 필요도 없고, 최대 6자리까지만 만들어봐도 이 문제를 해결하는데 문제 없을 것 같았다.

 

 그래서 반복문을 6까지만 돌려 실행시켜봤는데 역시 AC를 받았다.

 

문제에 대한 설명은 코드에 있다

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int answer = 9;
int goal, N;
 
void dfs(long long total, int cnt){
    // total의 범위는 cnt에 의해 알아서 고려되므로 신경쓰지 않아도 된다
    if(cnt >= answer) return;
    if(total == goal){
        answer = min(answer, cnt);
        return;
    }
    
    // N 이라는 수를 갯수에 맞게 처리해야된다
    // N 이 5일때 555의 경우 N을 3번 사용한게 된다
    // 결국 재귀를 돌릴 때 N을 몆번사용했는지와 그 값을 함께 넘겨야한다
    // N은 최대 8번까지 사용하라고 했으니
    // 만약 N이 9이고 8번이면 99999999 이 되고, 곱하기연산을 수행하게 되면
    // int의 범위를 벗어날 수 있으니 total는 long long을 사용한다
    int num = 0;
    for(int i = 1; i<9; i++){
        num *= 10, num += N;
        
        dfs(total + num, cnt + i);
        dfs(total - num, cnt + i);
        
        // N을 최소로 사용해야 하는데 만약 total이 0일 경우 곱하기나 나눗셈을 하면
        // 최소횟수를 만들 수 없다
        if(total != 0){
            dfs(total * num, cnt+i);
            dfs(total / num, cnt+i);
        }
    }
}
 
int solution(int n, int number) {
    // 재귀를 통해서 접근해보자
    N = n, goal = number;
    
    dfs(0, 0);
    answer = answer >= 9 ? -1 : answer;
    return answer;
}