백준 3687 성냥개비 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/3687

3687번: 성냥개비

문제

성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.

성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)

출력

각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. 

알고리즘 분류

• 다이나믹 프로그래밍
• 그리디 알고리즘

풀이

이 문제는 최댓값 구하는 건 쉬운데 최솟값을 구하는 게 좀 어려웠다.

dp문제는 초기 설정이 중요하다.

주어진 입력으로 무작정 최솟값, 최댓값을 구해보고, 이를 통해 점화식을 유추해야 한다.

 

우선 최댓값은 성냥의 개수를 2개로 최소로 사용하는 '1'을 이용해 자리수를 최대한 늘린다.

성냥의 개수가 짝수이면 '1'을 최대한 사용하면 되고, 성냥의 개수가 홀수이면 성냥의 개수를 3개로 사용하는 '7'을 맨 왼쪽에 붙이면 된다. 이를 maxDP에 저장하면, maxDP[2] = "1", maxDP[3] = "7"을 저장해놓고,

4 이상 100이하인 i에 대해

maxDP[i] = maxDP[i-2] + "1"을 하면 된다.

최댓값은 Long 자료형의 범위도 초과하니 문자열로 처리하자.

 

최솟값은 우선 성냥개비의 개수가 2~7인 경우를 먼저 구해보자.

arr[2] = 1

arr[3] = 7

arr[4] = 4

arr[5] = 2

arr[6] = 0

arr[7] = 8

minDP[2] = 1

minDP[3] = 7

minDP[4] = 4

minDP[5] = 2

minDP[6] = 6

minDP[7] = 8

2~7까지는 한 개의 숫자만 만들 수 있으므로 쉽게 구할 수 있기 때문에 이를 초기 조건으로 하고, 성냥개비가 6개일 땐 숫자가 0으로 시작할 수 없으니 최솟값이 6이 되고, 숫자가 두 자릿수가 넘어가면, 6개의 성냥개비로 0을 만들 수 있으니 이를 활용할 arr을 만들어준다.

성냥개비가 8이상인 경우를 구해보자.

성냥개비가 8개인 경우, 만약 성냥개비를 2개 사용하면 "1"가 되고, 남은 6개의 성냥개비로 "0"을 만들 수 있다. 

minDP[8] = minDP[8-2]*10+arr[2]

minDP[8] = minDP[8-3]*10+arr[3]

minDP[8] = minDP[8-4]*10+arr[4]

minDP[8] = minDP[8-5]*10+arr[5]

minDP[8] = minDP[8-6]*10+arr[6]

minDP[8] = minDP[8-7]*10+arr[7]

중에서 가장 작은 값이 최솟값이 된다.

따라서 점화식은 다음과 같다.

minDP[i] = min(minDP[i],minDP[i-j]*10 + arr[j])

minDP[1]은 없으니 minDP[8]까지만 값을 직접 구해 미리 넣어놓고, 성냥개비가 9개~ 100개일 때를

점화식을 통해 구하면 된다.

최솟값은 Long의 범위를 초과하지 않는다.

 

 

 

코드

import kotlin.math.*
fun main() =with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = Integer.parseInt(br.readLine())
    val minDP = LongArray(101){Long.MAX_VALUE}
    val maxDP = Array<String>(101){""}
    val arr = IntArray(8)
    arr[2] =1
    arr[3] =7
    arr[4] =4
    arr[5] =2
    arr[6] =0
    arr[7] =8
    minDP[2]=1
    minDP[3]=7
    minDP[4]=4
    minDP[5]=2
    minDP[6]=6
    minDP[7]=8
    minDP[8]=10
    for(i in  9 .. 100){
        for(j in 2 .. 7){
            minDP[i] = min(minDP[i],minDP[i-j]*10+arr[j])
        }
    }
    maxDP[2] = "1"
    maxDP[3] = "7"
    for(i in 4 ..100){
        maxDP[i] = maxDP[i-2]+"1"
    }

    for(i in 0 until n){
        val num = Integer.parseInt(br.readLine())
        write("${minDP[num]} ${maxDP[num]}\n")
    }
    close()
}