[Algorithm] Programmers :: 숫자 변환하기

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

프로그래머스

struct Node
{
    int num;
    int count;
};
 
bool visited[3000001] = { false };
 
int solution(int x, int y, int n)
{
    int answer = -1;
    
    queue<Node> q;
    q.push({ x,0 });
    
    while (!q.empty())
    {
        int curNum = q.front().num;
        int curCount = q.front().count;
        q.pop();
 
        if (curNum == y) return curCount;
        if (curNum > y) continue;
 
        if (!visited[curNum * 3])
        {
            visited[curNum * 3] = true;
            q.push({ curNum * 3, curCount + 1 });
        }
 
        if (!visited[curNum * 2])
        {
            visited[curNum * 2] = true;
            q.push({ curNum * 2, curCount + 1 });
        }
 
        if (!visited[curNum + n])
        {
            visited[curNum + n] = true;
            q.push({ curNum + n, curCount + 1 });
        }
    }
 
    return answer;
}

자연수 x에서 자연수 y까지 최소의 연산횟수를 구하는 문제이다.

dp를 적용해야 시간초과를 피할 수 있으며, 문제형태가 단순해서 위코드처럼 BFS말고도 그냥 for문 하나로도 해결할 수 있긴 하다. 값이 그냥 증가만하는 형태라서.. 여기서 좀 더 심화되면 값이 -가 되는 문제도 있다.