[6개월 안에 백준 플래티넘 달성하기] 5. 1로 만들기_1463 | 코틀린

 

Class 3 문제에 들어서면서 동적 계획법(DP) 문제들이 보이기 시작했습니다.

제가 처음 코테를 공부하기 시작하였을 때 벽을 느끼게 해 준 문제도 바로 DP문제였습니다. 아직도 많이 어렵지만 그래도 이제는 기본적인 DP문제들은 어느 정도 풀 수 있게 되었습니다.

 

그런 의미에서 DP의 기초문제 중 하나인 1로 만들기를 가져왔습니다.

 

 

다시 말해 주어진 정수 X를 위 3가지 연산을 최소로 사용하여 1로 만들면 됩니다.

 

 

DP문제는 가장 먼저 해당 문제 유형이 DP라는 것을 알아차리는 것이 중요하다고 생각합니다.

저는 처음에 이 문제가 DP인지 모르고 정수 X를 최소한의 방법으로 1로 만드는 수학적 규칙을 찾는 방향으로 문제를 풀었습니다. 물론 이러한 규칙은 존재하지 않았고 스트레스만 받고 끝났습니다.

 

풀이방법 

예시를 들면서 설명하겠습니다.

23이 주어졌을 때 정답은 23 -> 22 -> 21 -> 7 -> 6 -> 2 -> 1 순서가 됩니다.

 

여기서 중요한 것은 23의 최소 횟수를 구하기 위해서는

(22의 최소 횟수 + 1)을 하면 되며 마찬가지로 22의 최소 횟수를 구하기 위해서는

(21의 최소 횟수 + 1)를 하면 됩니다. 21의 최소 횟수를 구하기 위해서는

(7의 최소 횟수 + 1)를 하면 됩니다. 

이러한 메커니즘을 이해하시면 됩니다.

 

val input = 23  // 주어진 정수
val count = 0   // 계산 횟수

 

23은 3과 2로 나누어지지 않기 때문에 1을 빼줍니다. 이제 22일 때 최소 횟수를 구하면 됩니다.

count = 1, input = 22

 

22는 2로 나누어지며 또한 1을 뺄 수도 있습니다. 즉 두 방법 중 최소 횟수인 방법을 구하면 됩니다.

22 / 2 = 11의 최소 횟수 vs 21의 최소 횟수

count = 2, input = 11 or 21

 

11일 경우에는 1을 빼주는 경우만 있으며

21인 경우에는 3으로 나누거나 1을 빼주는 경우로 나뉩니다.

 

이런 식으로 3가지 계산의 모든 경우를 따지면서 최소 횟수일 경우만 골라가면 답을 구할 수 있습니다.

즉 23을 구하기 위해서는 min(23/3의 최소 횟수, 23/2의 최소 횟수, 23-1의 최소 횟수)을 구하면 됩니다.

23을 n이라고 하면 min(n/3의 최소 횟수, n/2의 최소 횟수, n-1의 최소 횟수)이라는 식이 완성됩니다.

 

마찬가지로 n/3의 최소 횟수를 구하기 위해서는 min(n/3/3의 최소 횟수, n/3/2의 최소 횟수, n/3-1의 최소 횟수)이라는 식이 완성되며 그 끝은 결국 1의 최소 횟수, 2의 최소 횟수, 3의 최소 횟수가 됩니다. 이 값은 우리가 직접 등록시켜 줘야 됩니다.

 

이제 추가적으로 신경 써줘야 되는 부분은 두 가지가 있습니다.

첫 번째로 각 숫자의 최소 횟수를 비교하기 위해서 최소 횟수를 담은 배열이 있어야 됩니다.

두 번째로 n이 3으로 나눠지는 경우인지 아닌지, 2로 나눠지는 경우인지 아닌지 체크해 줘야 됩니다. 나눠지지 않을 경우 비교에서 배제시킵니다.

 

이제 코드를 보겠습니다.

fun main() {
    val n = readln().toInt()
    val arr = IntArray(6000001)  // 각 정수 X에 대한 최소횟수를 담는 그릇
    arr[1] = 0
    arr[2] = 1
    arr[3] = 1                   // n/3의 경우를 체크하기 위한 최소한의 초기값.
    for (i in 4..n) {
        if (i % 3 == 0 && i % 2 == 0) {   // 3과 2 모두 나눠지는 경우
            arr[i] = Math.min(arr[i/3], arr[i/2]) + 1
        } else if (i % 3 ==0 && i % 2 != 0) {  // 3으로만 나눠지는 경우
            arr[i] = Math.min(arr[i/3], arr[i-1]) + 1
        } else if (i % 2 ==0 && i % 3 != 0) {  // 2로만 나눠지는 경우
            arr[i] = Math.min(arr[i/2], arr[i-1]) + 1
        } else {                               // 나눠지지 않는 경우
            arr[i] = arr[i-1] + 1
        }
    }
    print(arr[n])
}

 

가독성 있게 수정한 코드입니다.

 

fun main() {
    val n = readln().toInt()
    val arr = IntArray(6000001)
    arr[1] = 0
    arr[2] = 1
    arr[3] = 1
    for (i in 4..n) {
    	// 3가지 계산방법 비교
        var min = arr[i-1]
        if (i % 3 == 0) {
            min = Math.min(arr[i/3], min)
        }
        if (i % 2 == 0) {
            min = Math.min(arr[i/2], min)
        }
        arr[i] = min + 1
    }
    print(arr[n])
}

 

 

해당 문제를 예전에 처음 접했을 때는 손도 못 댈 정도로 어려워했었습니다. 그래도 지금은 쉽게 풀 수 있는 거 같아 다행인 거 같습니다.

경험상 문제를 많이 풀어보는 것 말고는 다른 방법이 없는 거 같습니다. 많이 풀다 보면 어느 정도 감이 생기는 거 같습니다. (단. 어려운 문제 제외)