Kotlin] 백준 1463번 문제풀이

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

1463번: 1로 만들기

 

 

이 문제는 동적 계획법으로 풀어야 한다.

 

https://itstudy-mary.tistory.com/580

동적 계획법(Dynamic Algorithm)(with. Kotlin)

 

그래서 저장해놓을 배열을 만들어두고, 해당 위치의 '전' 수식의 최솟값을 구한다.

 

예를 들어서 28을 한다고 가정하자.

28을 만들기 위해서는 14 * 2를 하면 된다. 즉, 14를 만들기 위한 최소 연산값에서 + 1을 하면 된다. 14 역시 7*2를 하면 된다. 즉, 7을 만들기 위한 최소 연산값에서 + 1을 하면 된다.

즉 28의 최소연산값은 14의 최소연산값, 7의 최소연산값, 6의 최소연산값, 2(혹은 3)의 최소연산값을 요구한다.

근데 또 잘 보면 28은 28 - 1을 하여 27을 하고, 27에서 3을 나누어 9, 9에서 3을 나누어 3, 3에서 1을 나누어 1로 가는 루트도 있다. 오히려 이 부분이 빠르다.

따라서, 해당 숫자에서 가질 수 있는 계산 경우의 수에서 저장되어있는 연산 최솟값을 가져와서 누가 더 작은지 비교한다.

 

그럼 여기서 비교할 수 있는 케이스가 무엇이 있을까?

- 2로 나누어질 경우, 2를 먼저 나누는 케이스와 -1을 하고 다음 연산자를 보는 케이스가 있다.

- 3으로 나누어질 경우, 3을 먼저 나누는 케이스와 -1을 하고 다음 연산자를 보는 케이스가 있다.

- 6으로 나누어질 경우, 2를 나누는 케이스, 3을 나누는 케이스, -1을 하고 나누는 케이스가 있다.

 

근데 여기서 6으로 굳이 나누어야 하나? 하고 물어볼 수 있는데, 이의 대표적인 반례가 30이다.

30

2로 먼저 나눌 경우 : 30 -> 15 -> 5 -> 4 -> 2 -> 1

3으로 나눌 경우 : 30 -> 10 -> 9 -> 3 -> 1

-1을 먼저 할 경우 : 30 -> 29 -> 28 -> 27 -> 9 -> 3 -> 1

 

다음과 같이 2로 먼저 나눌 경우와 3으로 먼저 나눌 경우 최소 연산값이 1이 차이 나기 때문에, 3을 나누는 것부터 먼저 하는 최솟값을 구해야한다.

 

가볍게 표에 저장된 예시 값을 보면서 다시 확인해보자.

(초기화)

2	3	4	5	6	7	8	9	10	11
0	0	0	0	0	0	0	0	0	0

 

 2와 3은 무조건 /2 혹은 /3으로 1을 만들 수 있으므로 1로 지정한다.

2	3	4	5	6	7	8	9	10	11
1	1	0	0	0	0	0	0	0	0

 

4의 경우 /2를 하는 케이스와 -1을 하는 케이스를 볼 수 있다.

/2를 하면 2, -1을 하면 3인데, 2의 최소연산값도 1, 3의 최소연산값도 1이므로 1+1 = 2를 넣어준다

2	3	4	5	6	7	8	9	10	11
1	1	2	0	0	0	0	0	0	0

 

5의 경우, 아무것도 나눌 수 없으므로 5-1 = 4의 최소 연산값을 가져온다. 따라서 2+1 = 3을 넣어준다.

2	3	4	5	6	7	8	9	10	11
1	1	2	3	0	0	0	0	0	0

 

6의 경우, 3가지 케이스를 가진다. 6/2 = 3, 6/3 = 2, 6-1 = 5. 3의 경우 최소 연산값 1, 2의 경우도 최소연산값 1, 5의 경우 3이므로, 6의 최소 연산값은 1+1 = 2가 된다.

2	3	4	5	6	7	8	9	10	11
1	1	2	3	2	0	0	0	0	0

 

7의 경우 아무것도 나눌 수 없으므로 7-1 = 6의 최소 연산값을 가져온다. 2+1 =3가 된다.

2	3	4	5	6	7	8	9	10	11
1	1	2	3	2	3	0	0	0	0

 

8의 경우 2로 나눈 것과 -1을 뺀 것을 비교한다. 8/2 = 4의 연산 최솟값 2, 8-1 =7 연산 최솟값 3을 비교하면 2를 나누는 것이 이득이므로 2+1 = 3이 된다.

2	3	4	5	6	7	8	9	10	11
1	1	2	3	2	3	3	0	0	0

 

 9의 경우 3으로 나눈 것과 -1을 뺀 것을 비교한다. 9/3 = 3의 연산 최솟값 1, 9-1 = 8의 연산 최솟값 3을 비교하면 3으로 나눈 것이 유리하므로 1+1 = 2가 된다

2	3	4	5	6	7	8	9	10	11
1	1	2	3	2	3	3	2	0	0

 

10의 경우, 2로 나눈 것과 -1을 뺀 것을 비교한다. 10/2 = 5의 연산 최솟값 3, 10-1 = 9의 연산 최솟값 2이므로, 1을 먼저 빼는 것이 유리하므로 2+1 = 3이 된다.

2	3	4	5	6	7	8	9	10	11
1	1	2	3	2	3	3	2	3	0

 

11의 경우 아무것도 나눌 수 없으므로 11-1 = 10의 연산최솟값 3 +1 = 4를 넣을 수 있다.

2	3	4	5	6	7	8	9	10	11
1	1	2	3	2	3	3	2	3	4

 

이렇게 전체 표를 다 구해놓고 원하는 값을 뽑아 쓰는 것이 하향식 접근(태뷸레이션)이다.

점화식은 (계산할 수 있는 케이스로 계산 후 테이블 값을 참조해서 최솟값을 구함 + 1)을 하는 것이 되겠다.

예를 들면 6을 구한다 가정하면

caseArray[6] = arrayOf(caseArray[6 / 2], caseArray[6 / 3], caseArray[6 - 1]).min() + 1

 

이렇게 연산 후의 값을 참조해 그 중 최솟값을 구하고, 그 최솟값에 +1을 해준다.

 

이를 식으로 쓰면

import kotlin.math.min

fun main(args: Array<String>) {
    question1463()
}

fun question1463() {
    val number = readln().toInt()

    val caseArray = Array(1000001) { 0 }
    caseArray[2] = 1
    caseArray[3] = 1

    for(i in 4 ..< caseArray.size) {
        if(i % 6 == 0) {
            caseArray[i] = arrayOf(caseArray[i / 2], caseArray[i / 3], caseArray[i - 1]).min() + 1
        } else if(i % 3 == 0) {
            caseArray[i] = min(caseArray[i / 3], caseArray[i - 1]) + 1
        } else if(i % 2 == 0) {
            caseArray[i] = min(caseArray[i / 2], caseArray[i - 1]) + 1
        } else {
            caseArray[i] = caseArray[i - 1] + 1
        }
    }

    println(caseArray[number])

}