C# 백준 3687 성냥개비 (동적계획법)

3687번: 성냥개비

IDEA

성냥개비는 2개부터 주어진다. 1개의 성냥개비로는 만들 수 있는 숫자가 없다. 각 숫자를 만드는데 필요한 성냥개비의 수는 다음과 같다.

1	2	3	4	5	6	7	8	9	0
2개	5개	5개	4개	5개	6개	3개	7개	6개	6개

큰수를 만들기 위해서는 가능한 자릿수를 많게, 앞자리를 크게 해주면 된다. 단 2개의 성냥개비만 있으면 자릿수를 하나씩 늘려버릴 수 있다. 한개만 더 있으면 맨 앞자리를 1에서 7로 바꿀 수 있다. 가장 큰 숫자를 만들기는 이렇게 간단히 정리가 된다. n이 짝수인 경우, 1을 n / 2 만큼 나열한다. n이 홀수인 경우 7을 하나 써놓고 그 뒤에 ( n - 3 / 2 ) 개의 1을 이어붙이면 된다.

 

작은 수를 만들어보자. 2개의 성냥개비로 만들 수 있는 가장 작은 수는 2다. 3개는 7, 4개는 4, 5개는 2, 6개는 0이지만 문제에서 가장 앞의 수가 0일 수 없다는 조건을 걸었기 때문에 성냥개비가 딱 6개만 주어졌다면 0이 아닌 6을 만들어야한다. 7개는 8이 가장 작다. 8개로 만들 수 있는 숫자는 2개와 6개로 만든 10, 3개와 5개로 만든 72, 4개와 4개로 만든 44, 5개와 3개로 만든 27, 6개와 2개로 만든 61 중 가장 작은 10이다. 9개로 만들 수 있는 숫자는 2개와 7개로 만든 18, 3개와 6개로 만든 70, 4개와 5개로 만든 42, 5개와 4개로 만든 24, 6개와 3개로 만든 67, 7개와 2개로 만든 81 중 가장 작은 18이다. n개의 성냥개비로 만들 수 있는 가장 작은 수는 i 가 2~7 까지 일 때 n - 2개와 i개의 성냥개비로 만든 숫자를 이어붙인 값 중 가장 작은 값이다. 그럼 대강 이런 식으로 코드를 작성할 수 있다.

for(int i = 8; i < n; i++)
{
	for(int j = 2; j < 8; j++)
    {
    	small[i] = Math.Min(small[i - j] * 10 + small[j], small[i]);
    }
}
// small 배열의 초기값을 모두 아주 큰 값으로 설정해야한다.
// 6개의 성냥개비의 예외를 따로 만들어줘야한다.
// i - j 값이 2보다 작아지는 경우는 계산하지 않아야한다.​

 

CODE

using System;
using System.Text;

class Program
{
    static int T, n;
    static long[] num = { 1, 7, 4, 2, 0, 8 };
    // 6 예외를 따로 생각하기 위한 이어붙이기 전용 배열
    static long[] small = new long[101];
    static StringBuilder large;
    static void Main()
    {
        T = int.Parse(Console.ReadLine());
        large = new StringBuilder();
        for(int i = 0; i < T; i++)
        {
            n = int.Parse(Console.ReadLine());
            for (int j = 2; j <= n; j++) small[j] = long.MaxValue;
            small[2] = 1; small[3] = 7; small[4] = 4;
            small[5] = 2; small[6] = 6; small[7] = 8;
            // n = 7까지의 초기값 미리 입력
            for (int j = 8; j <= n; j++)
            {
                for (int k = 2; k <= 7; k++)
                {
                    if (j - k < 2) continue;    // j - k 가 2보다 작은 경우는 생각하지 않는다.
                    if (small[j] > small[j - k] * 10 + num[k - 2]) small[j] = small[j - k] * 10 + num[k - 2];
                }
            }
            large.Append(small[n]);
            large.Append(" ");
            if (n % 2 == 0) large.Append("1");  // n 이 짝수인 경우 가장 앞에 1
            else large.Append('7');             // 홀수인 경우 가장 앞에 7
            large.Append('1', (n / 2) - 1);     // 나머지 성냥으로는 1만 만들어 이어붙인다.
            Console.WriteLine(large);
            large.Clear();
        }
    }
}