[Swift] 백준 1463 - 1로 만들기

문제 출처

처음 풀어본 다이나믹 프로그래밍 문제이다. 신기하당...

다이나믹 프로그래밍(동적계획법)이란?
큰 문제를 작은 문제로 나누어 풀이하는 방법

이 문제는 연산의 최솟값을 구하는 문제인데
dynamicArray 배열을 만들어 결정된 최솟값을 해당 배열안에 넣는다.

i 가 2부터 입력받은 숫자 num까지 1씩 증가한다고 할 때

• 만약 i가 3으로 나누어진다면
  연산의 최솟값은 dynamicArray[i/3] + 1 과 dynamicArray[i - 1] + 1 둘 중 더 작은 값이고
  그 값을 dynamicArray[i]에 넣는다.
• 만약 i가 2로 나누어진다면
  num의 연산의 최솟값은 dynamicArray[i/2] + 1 과 dynamicArray[i - 1] + 1 둘 중 더 작은 값이고 그 값을 dynamicArray[i]에 넣는다.
• 만약 i가 2와 3 둘 중 어느 것으로도 나누어지지 않는다면
  i연산의 최솟값은 dynamicArray[i - 1] + 1 이다.

최종적으로 num연산의 최솟값은 dynamicArray[num] 값이다.

따라서, 코드로 다음과 같이 작성할 수 있다.

import Foundation

var num = Int(readline()!)!
var dynamicArray = Array(repeating: 0, count: 1000001)
	
if num == 1 {
    print(0)
else { 
    for i in 2...num {
    	dynamicArray[i] = dynamicArray[i - 1] + 1
        
        if i%3 == 0 {
        	dynamicArray[i] = min(dynamicArray[i / 3] + 1 , dynamicArray[i])
        }
        
        if i%2 == 0 {
        	dynamicArray[i] = min(dynamicArray[i / 2] + 1 , dynamicArray[i])
        }
    }  
    print("\(dynamicArray[num]")
}