[코딩테스트] 23/12/14 - 숫자 변환하기 (Level2)

🌜 프로그래머스 링크

문제 설명

자연수 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

Github 링크

문제풀이

• BFS를 사용해서 경우의수를 계산한다.
• y에서 역으로 계산해야 나머지 경우의수를 줄이기 쉽다.

코드 (C++)

int solution(int x, int y, int n) {
    queue<pair<int, int>> q;
    q.emplace(y, 0);
    while (!q.empty())
    {
        pair<int,int> temp = q.front();
        q.pop();
        
        if (temp.first == x)
            return temp.second;
        
        if (temp.first % 2 == 0 && temp.first / 2 >= x)
            q.emplace(temp.first / 2, temp.second + 1);
        if (temp.first % 3 == 0 && temp.first / 3 >= x)
            q.emplace(temp.first / 3, temp.second + 1);
        if (temp.first - n >= x)
            q.emplace(temp.first - n, temp.second + 1);
    }
    return -1;
}