[백준(BOJ)] 1463 1로 만들기 - 스위프트(Swift)

[Silver III] 1로 만들기 - 1463

문제 링크

성능 요약

메모리: 87324 KB, 시간: 56 ms

분류

다이나믹 프로그래밍

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10⁶보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

풀이

연산의 최솟값을 구하는 문제이기 때문에 DP와 관련이 있을 것이라 예상하였고, 몇 가지의 수를 나열하여 규칙을 찾고자 하였습니다.

 

n	연산 과정	연산의 최솟값
1	x	0
2	2 -> 1	1
3	3 -> 1	1
4	4 -> 2 -> 1  or 4 -> 3 -> 1	2
5	5 -> 4 -> 2 -> 1 or 5 -> 4 -> 3 -> 1	3
6	6 -> 3 -> 1 or 6 -> 2 -> 1	2
7	7 -> 6 -> 3 -> 1 or 7 -> 6 -> 2 -> 1	3

규칙을 보고 4, 5, 6, 7과 같이 경우의 수가 나눠지는 경우 때문에 처음에 헷갈렸습니다.

 

우선 2로 나눌 수 있는 경우와 3으로 나눌 수 있는 경우 중에서는 3으로 나누는 것이 더욱 빠르게 1로 도달하기 때문에

효율적이라고 생각하였습니다. 

하지만 3의 배수에는 속하지 않지만 짝수인 경우의 수에는 2로 나누는 것이 훨씬 효율적이기 때문에

이에 대한 경우에는 2로 나눠주고자 하였습니다.

 

여기서 4에 대한 연산 과정을 살펴보겠습니다.

 

1. 4에서 2를 나눈다.

2. 2에서 1로 간다.

 

위 식을 해석해보자면 4에서 2로 나누는 연산이 한 번 나타나고, 2에서 1로 가는 것은 2에서의 연산의 최솟값을 나타낸 것입니다.

 

따라서 dp식을 구하는 식은 n을 구한다고 가정했을 때,

1. dp[n - 1]의 값으로 도달하기 위해 -1을 빼는 연산을 더한 dp[n - 1] + 1

2. 만약 나눠지는 것이 있다면 dp[n / 3] or dp[n / 2]의 값으로 도달하기 위해 연산을 한 번 더한 값

을 비교하여 최솟값을 dp배열에 추가해주면 됩니다.

 

다음은 코드로 작성한 값입니다.

import Foundation

var x = Int(readLine()!)!
var (dp, ans) = ([Int](repeating: 0, count: x+1), 0)   // 1 ~ 3 까지는 초기 설정

for i in 2..<x+1 {
    dp[i] = dp[i - 1] + 1   // 이전 단계에서 계산을 한 번 더 하는 것으로 설정
    
    if i % 3 == 0 { // 3의 배수 -> dp[i / 3]로 이동하고(+1) 해당 값 출력
        dp[i] = min(dp[i], dp[i / 3] + 1)
    }
    
    if i % 2 == 0 { // 짝수일 때 -> dp[i / 2]로 이동하고(+1) 해당 값 출력
        dp[i] = min(dp[i], dp[i / 2] + 1)
    }
    
}

print(dp[x])

dp배열에는 계속해서 최솟값을 계산하기 때문에, dp[i / 3]이나 dp[i / 2]와 같은 값이 최솟값입니다.