백준 [3687] kotlin

[문제]

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

3687번: 성냥개비

 

[풀이]

최대와 최소를 나누어 풀었다.

 

[최대]

최대는 간단하다. 성냥개비를 2개를 사용하여 만들 수 있는 숫자는 1이다.

1개로 만들 수 있는 숫자는 없으므로,

임의의 숫자를 A라고 했을 때  A = (2 * n) + 3 으로 이루어져 있다고 볼 수 있다. 

 

사용할 수 있는 성냥개비를 N이라고 하고, N을 2로 나누었을 때 몫을 a, 나머지를 b라고 하였을 때

1. a가 1이면 (N이 홀수인 경우)

최대는 7 과 1이 a-1개가 있는 숫자로 표현할 수 있다.

2. a가 0이면 (N이 짝수인 경우)

최대는 1이 a개가 있는 숫자로 표현할 수 있다.

 

[최소]

최소는 DP를 이용하여 풀었다.

0~9까지 숫자는 성냥개비 2~7개를 이용하여 만들 수 있다. 

2~7개를 이용하여 만들 수 있는 숫자중에 가장 작은 숫자를을 저장해둔 배열을 만든다면 그 배열을 matches라고 하면

matches = [1,7,4,2,0,8]이다.

 

matches의 인덱스를 j라고 하면,

i개로 만들 수 있는 성냥의 최소는 dp[i] = min(dp[i], dp[i-j-2] * 10 + matches[j])로 표현할 수 있다.

 

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.min

var minMatches = listOf(1,7,4,2,0,8)
var matchNum = listOf(2,3,4,5,6,7)
var ans : Long = 0
lateinit var maxMatch : String
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    val T = br.readLine().toInt()

    var dp = LongArray(101) { Long.MAX_VALUE }
    for (i in matchNum.indices) dp[matchNum[i]] = minMatches[i].toLong() 
    dp[6] = 6
    dp[1] = Int.MAX_VALUE.toLong()
    for(i in 8..100)
    {
        for(j in matchNum.indices)
        {
            dp[i] = min(dp[i], dp[i - j - 2] * 10 + minMatches[j])
        }
    }
    repeat(T)
    {
        val tmp = br.readLine().toInt()

        /* 최대 구하기 */
        maxMatch = ""
        if(tmp % 2 == 0)
        {
            repeat(tmp/2)
            {
                maxMatch += "1"
            }
        }
        else
        {
            maxMatch += "7"
            repeat(tmp/2-1)
            {
                maxMatch += "1"
            }
        }
        /* 최소 구하기 */
        val minMatch = dp[tmp]
        bw.write("$minMatch $maxMatch\n")
    }
    bw.flush()
    bw.close()
}