[Algorithm] 1로 만들기

[hwangJi-dev]

💬 문제

https://www.acmicpc.net/problem/1463

💬 Idea

• 2부터 X까지 차례대로 연산의 최소 횟수를 저장해나간다.
• 이전 수의 연산횟수에서 1을 더한다 의 의미는
  • == 이전 수로 갈 때 -1 연산을 수행할 수 있다
  • == 이전 수로 갈 때 //2 연산을 수행할 수 있다 (2로 나눌 수 있다는 가정 하에)
  • == 이전 수로 갈 때 //3 연산을 수행할 수 있다 (3으로 나눌 수 있다는 가정 하에)
• 이므로 해당 3가지 경우의 최솟값을 숫자의 배열 인덱스에 저장해나가면 큰 수에 적용하여도 연산의 횟수가 도출된다.

💬 풀이

import Foundation

func solution1463() {
    let X = Int(readLine()!)!
    var minCalArr = Array(repeating: 0, count: X + 1)
    
    if X == 1 {
        print(0)
    } else {
        for i in 2...X {
            minCalArr[i] = minCalArr[i - 1] + 1 // 이전 수의 연산횟수에서 1을 더한다 == 이전 수로 갈 때 -1 연산을 수행한다
            
            if i % 2 == 0 {
                minCalArr[i] = min(minCalArr[i], minCalArr[i / 2] + 1)
            }
            
            if i % 3 == 0 {
                minCalArr[i] = min(minCalArr[i], minCalArr[i / 3] + 1)
            }
            
            // -1, //2 //3 연산 중 가장 작은 연산횟수가 i의 최소 연산횟수가 된다.
        }
        
        print(minCalArr[X])
    }
}