[swift] 백준 - 1463번: 1로 만들기

1463번: 1로 만들기

---

나의 풀이

var num = Int(readLine()!)!
var arr = Array(repeating: 0, count: num+1)
for i in 1...num {
    if i == 1 { continue }
    arr[i] = arr[i-1]+1 // 1을 뺏을 때
    if i % 3 == 0 { arr[i] = min(arr[i], arr[i/3]+1) } // 3으로 나눠질 때
    if i % 2 == 0 { arr[i] = min(arr[i], arr[i/2]+1) } // 2로 나눠질 때
}
print(arr[num])

풀이 키워드

DP
2부터 최소로 1까지 도달 할 수 있는 숫자를 arr배열에 저장하면서 반복문을 돌려줍니다.
최소로 도달 할 수 있는 조건은
i - 1의 최소 도달거리 + 1
i가 3으로 나눠질 때 i / 3의 최소 도달거리 + 1
i가 2로 나눠질 때 i / 2의 최소 도달거리 + 1
최대 3가지의  조건 중 제일 작은 수를 해당하는 인덱스를 arr에 저장합니다.

---