[Programmers] 숫자 변환하기 [c++]

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

---

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

---

입출력 예

x y n result

10	40	5	2
10	40	30	1
2	5	4	-1

---

문제 해결 접근법

• 문제의 목표는 x 에서 시작하여 y 에 도달하는 최단거리를 찾는것과 같다.
• x 와 y 를 모두 알고 있으니 y 에서 x까지의 최단거리를 구할 수 있다
• 이와 같이 연산을 역순으로 진행하게 되면 가능한 상태의 수가 줄어든다
• 각 수마다 최대 3가지 분기점이 있다
  • 3으로 나누는 경우
  • 2로 나누는 경우
  • n 으로 빼는 경우
• 만약 x → y 방향으로 진행했다면 모든 경우의 수를 다 확인 해야 했을 것이다
• 하지만 y → x 방향으로 진행할 시, 다음과 같은 경우는 확인하지 않아도 된다
  • y % 3 ≠ 0
  • y % 2 ≠ 0

#include <bits/stdc++.h>
using namespace std;

int ans = INT_MAX;

int solution(int x, int y, int n) {
    if (y == x) return 0;
    
    set<int> v;
    queue<pair<int,int>> q;
    q.push({y, 0});
    v.insert(y);
    
    while(!q.empty()) {
        int current = q.front().first;
        int cost = q.front().second;
        q.pop();
        
        if(current == x) {
            return cost;
        }
        
        if(current % 3 == 0 && current / 3 >= x && !v.count(current/3)) {
            v.insert(current/3);
            q.push({current/3, cost + 1});
        }
        if(current % 2 == 0 && current / 2 >= x && !v.count(current/2)) {
            v.insert(current/2);
            q.push({current/2, cost + 1});
        }
        if(current - n >= x && !v.count(current - n)) {
            v.insert(current - n);
            q.push({current - n, cost + 1});
        }
    }
    
    if (ans == INT_MAX) ans = -1;
    return ans;
}