[백준] 1로 만들기 - 실버 3 (Kotlin)

김민형·2022년 6월 21일
0

백준 알고리즘

목록 보기
3/13

문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

풀이

상향식 DP 를 사용하려고 생각했다.
구하고자 하는 값이 횟수의 최솟값이므로 DP Table (1차원 배열) 의 값은 최솟값을 저장한다.

  • A[1] = 0
    • 1 은 그 자체가 1 이므로 연산횟수는 0 이다.
  • A[2] = 1
    • 2 는 -1 혹은 /2 하면 1 이 되므로 최소 연산횟수는 1 이다.
  • A[3] = 1
    • 3 은 /3 의 경우에 1 이 되므로 최소 연산횟수는 1 이다.
  • 4 이후로는 /3 혹은 /2 혹은 -1 한 값의 최솟값에 각 +1 을 한 뒤 그 중 최솟값을 저장한다.
    • A[4/3] 은 불가능 하므로 패스, A[4/2] = A[2] = 1 이고 +1 하여 2,
      A[4-1] = A[3] = 1 이고 +1 하여 2
    • Min(불가능, 2, 2) 하여 A[4] = 2
  • 이런 식으로 문제의 예시에 나온 10 을 계산해보면
    • A[10/3] = 불가능, A[10/2] = A[5] = 3, A[10-1] = A[9] = 2
    • 따라서, A[10] = Min(불가능, 4, 3) = 3

소스 코드

const val INF = 987654321
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val dp = IntArray(10000001) {INF}

    dp[1] = 0
    dp[2] = 1
    dp[3] = 1

    for (i in 4..N) {
        if (i%3 == 0) {
            dp[i] = Math.min(dp[i/3]+1, dp[i])
        }
        if (i%2 == 0) {
            dp[i] = Math.min(dp[i/2]+1, dp[i])
        }
            dp[i] = Math.min(dp[i-1]+1, dp[i])
    }

    println(dp[N])

}
profile
Stick To Nothing!

0개의 댓글