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

문제 풀이 아이디어

딱 보면 알 수 있는 것은 아니지만 읽어보면 결국은 최단 경로 문제입니다. x에 n을 더하기, 2를 곱하기, 3을 곱하기의 3가지 경우의 수를 통해서 y에 도달하는 최단 경로를 구하면 됩니다.

주의해야 할 점은 y의 최대값이 1,000,000이라는 점입니다. O(N) 이하의 시간복잡도를 가진 알고리즘만을 사용해서 풀어야 합니다.

BFS

최단 경로를 찾는 것을 생각해보면 가장 먼저 떠오르는 방법은 bfs를 사용하는 방법입니다. 방문한 숫자를 다시 방문하지 않도록 visited 배열을 사용했습니다.

// swift로 큐 구현
struct Queue {

    var index = 0
    var queue = [(Int, Int)]()

    var isEmpty: Bool {
        queue.count ==  index
    }

    mutating func push(_ new: (Int, Int)) {
        queue.append(new)
    }

    mutating func pop() -> (Int, Int) {
        defer {
            index += 1
        }
        return queue[index]
    }
}

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    // 반복문 내에서 사용할 연산 배열
    let operations: [(Int) -> Int] = [
        { x in x + n },
        { x in x * 2 },
        { x in x * 3 }
    ]

    // bfs 구현
    var queue = Queue()
    var visited = Array(repeating: false, count: y + 1)
    queue.push((x, 0))
    visited[x] = true

    while !queue.isEmpty {
        let (now, cost) = queue.pop()

        // y에 도달하는 최단 경로 리턴
        if now == y {
            return cost
        }

        // 3가지 경로를 모두 완전 탐색
        for operation in operations {
            let new = operation(now)
            if new <= y && !visited[new] {
                queue.push((new, cost + 1))
                visited[new] = true
            }
        }

    }

    // 최단 경로를 못 찾음
    return -1
}

DP

DP를 사용해서 풀 수도 있습니다. 초기값과 점화식은 아래와 같습니다.

초기값: 
	f(x) = 0 (시작값인 x는 연산 0회)
점화식:
	f(x + n) = f(x) + 1
	f(x * 2) = f(x) + 1
	f(x * 3) = f(x) + 1

코드로 구현하면 아래와 같습니다.

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    
    // 3가지 연산 정의 (반복문용)
    let operations: [(Int) -> Int] = [
        { x in x + n },
        { x in x * 2 },
        { x in x * 3 }
    ]
    
    // dp 배열 (index까지 가는데 최단 경로 저장)
        // x가 1이고 y가 1000000, n이 1일 때
        // 최대 답이 최대값이 999999이므로 기본값을 1000000로
    var dp = Array(repeating: 1000000, count: y + 1)
    
    // 출발점인 x의 초기값이 0
    dp[x] = 0
    
    for now in x..<y {
        // 3가지 연산을 실시
        for operation in operations {
            let next = operation(now)
            // 연산을 실시한 값이 y보다 작을 때 경로 저장 (연산을 통해 작아질 수는 없으므로)
            if next <= y {
                // 최단 경로 갱신
                dp[next] = min(dp[next], dp[now] + 1)
            }
        }
    }
    
    // 최단경로가 기본값이면 (연산할 수 없음), 아니라면 답 리턴
    return dp[y] == 1000000 ? -1 : dp[y]
}

실행 속도

왼쪽이 bfs, 오른쪽이 dp의 실행 결과입니다. 아무래도 bfs는 최단 경로를 구하는 순간 바로 리턴하기 때문에 좀 더 빠릅니다.