[프로그래머스] 숫자 변환하기 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

풀이 방법

x를 x+n, x*2, x*3을 통해 y를 DFS로 만드는 것보다

y를 y-n, y/2, y/3 를 통해 x를 만드는 방식이 더욱 효율적이다.

 

왜냐하면 y를 /2, /3 할 때 딱 나눠 떨어지지 않는 경우를 가지를 칠 수 있기 때문이다.

y를 /2 또는 /3으로 나누었을 때 딱 나누어 떨어지지 않으면 x를 x2 x3 하여 y를 만들 수 없기 때문이다.

 

또한 방문 여부를 통해 순환호출을 제어하는 로직을 작성한다면 안된다.

왜냐하면 먼저 방문하여 N번의 횟수로 수를 만들었다 하더라도

이후의 탐색 결과로 더 낮은 횟수로 만들 수 있는 방법이 나올 수 있기 때문이다.

 

그래서 방문 여부가 아닌 그 수를 만드는데 들었던 연산 횟수를 기록한다.

어떤 수 N을 만들 때 M번 연산을 하였다면

다음에 어떤 수 N을 방문할 때 M번 연산한 횟수보다 작으면 방문하는 것이다.

왜냐하면 M번 연산한 횟수보다 많은 횟수로 수 N을 만들었다면 그 연산 과정은 최소가 아닌 연산 과정이라 답을 구하는 과정에 필요가 없기 때문이다.

 

예를 들어

우리는 현재 num 값을 만드는데 드는 연산 횟수 cnt가 있다.

여기서 num-1 값을 만드는데 드는 연산 횟수는 cnt+1이다. 왜냐 -1 연산을 한번 하면 되니깐.

DP[num-1]에는 num-1을 만드는데 드는 연산 횟수가 저장되어 있다.

여기에 cnt+1보다 큰 값이 들었다면 지금 연산 횟수 cnt+1은 num-1을 만드는데 최소가 되는 연산 횟수가 된다는 것이다.

 

전체 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

int solution(int x, int y, int n) {
    int answer = 0;
    int dp[1000001];
    fill(dp, dp+1000001, 9999999);
    stack<pair<int,int>> s;
    s.push(make_pair(y,0)); // 현재 y 값부터 탐색 시작
    
    
    // 테스트 케이스 6번이 틀려버린다. x y가 동일한 경우
    
    
    while(!s.empty()) {
        int num = s.top().first;
        int cnt = s.top().second;
        s.pop();
        
        
        if(num-n>=x && dp[num-n]>cnt+1) {
            s.push(make_pair(num-n, cnt+1));
            dp[num-n]=cnt+1;
        }
        
        if(num%2==0 && dp[num/2]>cnt+1) {
            s.push(make_pair(num/2, cnt+1));
            dp[num/2]=cnt+1;
        }
        
        if(num%3==0 && dp[num/3]>cnt+1) {
            s.push(make_pair(num/3, cnt+1));
            dp[num/3] = cnt+1;
        }
        
    }
    
    answer = dp[x];
    if(answer == 9999999) { // dp[x]가 9999999인 경우 x를 만들 수 없는것임.
        answer = -1;
    }
    
    if(x==y) // x y가 동일한 경우
        answer=0;
    
    return answer;
}