[Swift] 백준_1로 만들기(1463)

문제

 

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

1463번: 1로 만들기

 

 

풀이

 

다이나믹 프로그래밍 문제들을 풀어보기 시작하였다.

 

이 문제를 처음봤을 땐 bfs풀이만 생각했었다. 3으로 나눈 경우, 2로 나눈 경우, 1을 뺀 경우를 각각 큐에 넣어 1이 만들어졌을 때 결과를 출력하면 되는데 실제로 구현해보니 시간초과가 나왔다.

 

이 문제는 dp로 해결해야한다. 

 

dp가 이전의 연산 값을 이용해서 문제를 푸는 건 알겠는데, 어떤 문제를 dp로 해결해야할지는 잘 모르겠다.

 

일단 점화식을 구하면, 임의의 수 k부터 1까지 만드는 최소 횟수를 구하기 위해선 k - 1, k / 2, k / 3부터 1까지 만드는 각각의 횟수에서 1을 더한 값 중 최소값을 구하면 된다. 

 

k가 1일때는 0인 것을 이용하여 해결할 수 있었다.

import Foundation

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

 

 

____________________________________________________________________________________________________

 

 

어떤 문제를 dp로 해결해야되는지 모르겠음.