[백준] 1229 - 육각수

1. 문제

1229번: 육각수

2. 개요

점 N개를 가지는 육각수의 최소 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

육각수는 1, 6, 15, 28, 45 … 의 -4 + 5 + 4 * i 로 나타낼 수 있고,

점 N개를 가지는 육각수는 그보다 작은 점의 개수를 가지는 경우의 조합으로 나타낼 수 있다.

예로 i = 35의 경우에는

1. 점 1개짜리 육각수 1개 + 점 34개로 만드는 최소 개수
2. 점 6개짜리 육각수 1개 + 점 29개로 만드는 최소 개수
3. 점 15개짜리 육각수 1개 + 점 20개로 만드는 최소 개수
4. 점 28개짜리 육각수 1개 + 점 7개로 만드는 최소 개수

가 된다.

즉 작은 육각수부터 탐색하며 dp를 하나씩 갱신해나가면 된다.

또한 문제에서 나올 수 있는 최댓값은 6이라고 하였으므로 초기값은 이를 활용한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

dp = [0, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 2]
nums = [0]

for i in range(707):
    nums.append(nums[i] + -4 + 5 + 4 * i)

if N < 13:
    print(dp[N])

else:
    for i in range(13, N + 1):
        dp.append(6)
        for num in nums:
            if num > i:
                break
            dp[i] = min(dp[i - num] + 1, dp[i])

    print(dp[N])

3-3. C#

namespace boj_1229
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            List<int> dp = new List<int> { 0, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 2 };

            if (N < 13)
                Console.WriteLine(dp[N]);

            else
            {
                List<int> nums = new List<int> { 0 };
                for (int i = 0; i < 707; i++)
                    nums.Add(nums[i] - 4 + 5 + 4 * i);

                for (int i = 13; i < N + 1; i++)
                {
                    dp.Add(6);
                    foreach (int num in nums)
                    {
                        if (num > i) break;

                        dp[i] = Math.Min(dp[i - num] + 1, dp[i]);
                    }
                }

                Console.WriteLine(dp[N]);
            }
        }
    }
}