[2023-04-22] 1463 1로 만들기(Kotlin) + 1문제

 

문제 링크: https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

드디어 dp 문제를 제 스스로 풀었습니다. 너무 행복합니다 ㅎㅎ.

 

 

작성 코드입니다.

 

// 4를 1로 만드는 횟수의 최소,
// 5를 1로 만드는 횟수의 최소...
// 이렇게 생각을 해보니 1 부터 n까지
// 최소 횟수를 쌓아놓아야 겠다는 생각이 들었다.
// dp[4] = 2, dp[5] = 3 ....
//
// 계산 가능한 경우의 수는 3으로 나누기, 2로 나누기, 1 빼기 이므로
// 각 연산을 진행하여 나온 수가 최솟값일 경우를 배열에 쭉 저장한다.
// ex) 6
// dp[6 / 3] = 1, dp [6 / 2] = 1, dp[6 - 1] = 3
// 따라서 dp[6] = 1 + 1(= 연산 1회)


package twentyTwoThDay
import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val dp =  Array(n+1){0}
    
    // 입력에 1이 들어올 수 있으므로 예외처리를 해주었다.
    if (n <= 3)
        if (n==1)
            println(0)
        else
            println(1)
            
    else{
        dp[1] = 1
        dp[2] = 1
        dp[3] = 1
        for (index in 4 .. n){
        	// 3과 2로 둘 다 나누어 떨어질 경우
            // 3으로 나눈 값, 2로 나눈 값, 1을 빼준 값 모두 비교
            if (index % 3 == 0 && index % 2 == 0)
                dp[index] = Math.min(Math.min(dp[index/3], dp[index/2]),dp[index-1]) + 1
                
            // 3으로만 나누어 떨어질 경우
            // 3으로 나눈 값, 1을 빼준 값 비교
            else if (index % 3 == 0)
                dp[index] = Math.min(dp[index/3], dp[index-1]) + 1
                
            // 2로만 나누어 떨어질 경우
            // 2로 나눈 값, 1을 빼준 값 비교
            else if (index % 2 == 0)
                dp[index] = Math.min(dp[index/2], dp[index-1]) + 1
            
            else
                dp[index] = dp[index-1] + 1
        }
        println(dp[n])
    }
}

 

 

99퍼에서 틀렸다고 나와, 환호성을 지르다 말았습니다.

 

입력 조건이 1보다 크거나 같다고 했으므로, 1이 들어갈 경우 0을 출력하게 해주었습니다.