[백준/Swift] 1463번: 1로 만들기

 

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

1463번: 1로 만들기

 

X에서 사용하는 연산

1. 3으로 나누어 떨어지면, 3으로 나누기
2. 2로 나누어떨어지면 2로 나누기
3. 1 빼기

연산을 사용하는 횟수의 최솟값

 

1~N을 쭉 보면서 저 연산들을 사용해서 1을 만들 수 있는 방법의 횟수 최솟값 구하기

• 2의 배수
  • min(2로 나눈 값, 이전 dp + 1)
• 3의 배수
  • min(3로 나눈 값, 이전 dp + 1)
• 나머지
  • 이전 dp + 1회

3의 배수 먼저! 큰 애를 먼저 나눠야 횟수가 적음

 

import Foundation

//input
let n = Int(readLine()!)!
var dp = [Int](repeating: 0, count: 1000001)
dp[1] = 0
if n >= 2 {
    for i in 2...n {
        dp[i] = dp[i-1] + 1
        if i % 3 == 0 {
            dp[i] = min(dp[i], dp[i/3] + 1)
        }
        if i % 2 == 0 {
            dp[i] = min(dp[i], dp[i/2] + 1)
        }
    }
}
print(dp[n])