작성일자 : 2022-04-23
수정일자 : 2022-04-23

링크 : 1463번: 1로 만들기

1로 만들기

문제

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

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

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

입력

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

출력

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

---

참고 사항

큰 수로 나누는 것이 무조건 작을 것으로 생각할 수 있는데, 10에서 해당 생각의 문제점을 찾을 수 있다.

나눗셈 먼저 진행 : 10÷2=5 / 5-1=4 / 4÷2=2 / 2÷2=1 (4회)
뺄셈 먼저 진행 : 10-1=9 / 9÷3=3 / 3÷3=1 (3회)

즉, 10의 결과를 구하기 위해서 9의 결과가 필요하고, 9에서는 3의 결과를, 3에서는 1의 결과를 필요로 하는 이전 연산 값을 재사용하고 초기 설정 값이 명확한 상향식 다이나믹 프로그래밍으로 해결하는 것이 좋다고 할 수 있다.

---

예제 소스 코드

Kotlin

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

fun main() {
    BufferedReader(InputStreamReader(System.`in`)).use { reader ->
        val input = reader.readLine()
        val x = input.toInt()

        val dp: MutableList<Int> = mutableListOf(0, 0)
        for (i in 2 .. x) {
            dp.add(dp[i - 1] + 1)

            if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1)
            if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1)
        }

        println(dp[x])
    }
}

---

풀이

표로 이해하기

1~10까지의 수를 1로 만드는 최소 횟수를 표로 풀어서 정리하면 다음과 같다.

값	가능한 연산 (÷3 or ÷2 or -1)	1로 만드는 최소 횟수 (min(÷3, ÷2, -1))
1	-	0
2	2÷3 => 계산 불가능 2÷2=1 => 1이 1이 되는 최소 횟수 + 1 2-1=1 => 1이 1이 되는 최소 횟수 + 1	- (1의 최소)0+1 (1의 최소)0+1 min=1
3	3÷3=1 => 1이 1이 되는 최소 횟수 + 1 3÷2 => 계산 불가 3-1=2 => 2가 1이 되는 최소 횟수 + 1	(1의 최소)0+1 - (2의 최소)1+1 min=1
4	4÷3 => 계산 불가 4÷2=2 => 2가 1이 되는 최소 횟수 + 1 4-1=3 => 3이 1이 되는 최소 횟수 + 1	- (2의 최소)1+1 (3의 최소)1+1 min=2
5	5÷3 => 계산 불가 5÷2 => 계산 불가 5-1=4 => 4가 1이 되는 최소 횟수 + 1	- - (4의 최소)2+1 min=3
6	6÷3=2 => 2가 1이 되는 최소 횟수 + 1 6÷2=3 => 3이 1이 되는 최소 횟수 + 1 6-1=5 => 5가 1이 되는 최소 횟수 + 1	(2의 최소)1+1 (3의 최소)1+1 (5의 최소)3+1 min=2
7	7÷3 => 계산 불가 7÷2 => 계산 불가 7-1=6 => 6이 1이 되는 최소 횟수 + 1	- - (6의 최소)2+1 min=3
8	8÷3 => 계산 불가 8÷2=4 => 4가 1이 되는 최소 횟수 + 1 8-1=7 => 7이 1이 되는 최소 횟수 + 1	- (4의 최소)2+1 (7의 최소)3+1 min=3
9	9÷3=3 => 3이 1이 되는 최소 횟수 + 1 9÷2 => 계산 불가 9-1=8 => 8이 1이 되는 최소 횟수 + 1	(3의 최소)1+1 - (8의 최소)3+1 min=2
10	10÷3 => 계산 불가 10÷2=5 => 5가 1이 되는 최소 횟수 + 1 10-1=9 => 9가 1이 되는 최소 횟수 + 1	- (5의 최소)3+1 (9의 최소)2+1 min=3

식으로 이해하기

점화식 규칙을 적용해보면 다음과 같다.

1. 3으로 나누어 떨어질 때 : D[N] = D[N/3] + 1
2. 2로 나누어 떨어질 때 : D[N] = D[N/2] + 1
3. 1을 뺄 때 : D[N] = D[N-1] + 1

이 조건 중 최솟값을 추출하면 된다. 식으로 정리하면 다음과 같다.

코드로 이해하기

val dp: MutableList<Int> = mutableListOf(0, 0)
for (i in 2 .. x) {
    dp.add(dp[i - 1] + 1)

    if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1)
    if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1)
}

1. val dp: MutableList<Int> = mutableListOf(0, 0)
   메모이제이션을 위한 배열을 선언한다. val dp = IntArray(1000001) 정적 배열로 선언해도 상관없다(다만 3줄의 dp.add(dp[i - 1] + 1) 코드를 dp[i] = dp[i - 1] + 1로 변경해야 함). 0번째에 0을 넣은 이유는 배열 순서 매칭 편의성을 위해서이고, 1번째에 0을 넣은 이유는 1번째는 적용할 식이 없기 때문에 0을 넣었다.
2. for (i in 2 .. x) {...}
   상향식 다이나믹 프로그래밍 적용을 위한 반복문을 실행한다. 2부터 x 이하까지 반복하는 조건(2 ≤ i ≤ x)이다.
3. dp.add(dp[i - 1] + 1) // 혹은 dp[i] = dp[i - 1] + 1
   점화식 규칙 3번(D[N-1] + 1)을 적용한다. 이 규칙은 언제나 적용되는 규칙이기 때문에 먼저 적용한다.
4. if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1)
5. if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1)
   점화식 규칙 2(D[N] = D[N/2] + 1)번, 점화식 규칙 1(D[N] = D[N/3] + 1)번을 적용한다. 적용 후 이전 코드에 적용했던 규칙 3번과 새로 적용한 규칙 중 횟수가 더 작은 것으로 저장한다.