[Gold IV] 육각수 - 1229
성능 요약
메모리: 39504 KB, 시간: 152 ms
분류
다이나믹 프로그래밍, 수학, 런타임 전의 전처리
문제 설명
육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, ..., n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다.
그림 1
그림1은 h1, h2, h3, h4를 의미하며, 처음 육각수 6개는 1, 6, 15, 28, 45, 66이다.
자연수 N이 주어졌을 때, 합이 N이 되는 육각수 개수의 최솟값을 구해보자.
| N | 최소 개수 | 합 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1+1 |
| 3 | 3 | 1+1+1 |
| 4 | 4 | 1+1+1+1 |
| 5 | 5 | 1+1+1+1+1 |
| 6 | 1 | 6 |
| 7 | 2 | 1+6 |
| 8 | 3 | 1+1+6 |
| 9 | 4 | 1+1+1+6 |
| 10 | 5 | 1+1+1+1+6 |
| 11 | 6 | 1+1+1+1+1+6 |
| 12 | 2 | 6+6 |
1791보다 큰 정수는 항상 육각수 4개의 합으로 만들 수 있다. 또한, 수가 충분히 크다면 항상 육각수 3개의 합으로 만들 수 있다. 또, 최소 개수는 항상 6 이하이고, 이것이 최소인 N은 11과 26밖에 없다. 답이 6인 가장 큰 N은 26, 5인 가장 큰 N은 130, 4인 가장 큰 N은 146858이다.
입력
첫째 줄에 N이 주어진다.
출력
첫째 줄에 N을 만들기 위해 필요한 육각수 개수의 최솟값을 출력한다.
풀이
아이디어
처음 육각수의 개수 1, 6, 15, 28, 45, 66은 첫 항이 5이고 d가 4인 등차수열이다.
수열을 만드는데 가장 큰 수가 n보다 작을떄까지만 생성한다.
위 수식을 일반항으로 바꾸어보면 다음 식이 성립한다.
이를 기반으로 수열의 최댓값이 보다 작을때까지 생성한 후 그 수열을 기반으로 다이나믹 프로그래밍을 진행한다. 원리는 완전탐색이다.
그렇게 해서 나온 솔루션은 다음 코드를 따른다. 하지만 조금 더 최적화 된 방법을 생각해보아야 한다.
import sys
sys.setrecursionlimit(int(1e9))
MAX = float('INF')
n = int(input())
dp = [0] * (n+1)
ar = []
i = 1
while (t:=2*i**2 - i) <= n:
ar.append(t)
i += 1
def solve(k):
if k <= 0:
return 0
if dp[k] != 0:
return dp[k]
dp[k] = MAX
for i in ar:
if i > n:
continue
dp[k] = min(dp[k], solve(k-i) + 1)
return dp[k]
print(solve(n))문제가 괜히 런타임 전의 전처리가 아닐 것이다.
다음부터의 풀이는 해당 블로그를 참조했다.
전처리가 가능한 이유는 문제에서 n이하 값들에 대한 수를 보장해주었기 떄문에, 미리 규칙을 찾아 5개인 값, 4개인 값, 3개인 값, 2개인 값을 찾아 DP 테이블에 저장하는 방식이다.
코드
DP = [0 for _ in range(1000001)]
hexagon = [2*i*i - i for i in range(1, 708)]
hex_set = set(hexagon)
for i in range(707):
a = hexagon[i]
for j in range(i, 707):
b = hexagon[j]
if a+b > 1000000:
break
DP[a+b] = 2
for i in hexagon:
DP[i] = 1
DP[11], DP[26] = 6, 6
five = [5, 10, 20, 25, 38, 39, 54, 65, 70, 114, 130]
four = [4, 9, 14, 19, 23, 24, 32, 33, 37, 41, 42, 48, 50, 53, 55, 59, 63, 64, 69, 76, 77, 80, 83, 85, 86, 89, 99, 102, 104, 108, 110, 113, 115, 116, 123, 124, 128, 129, 131, 140, 143, 144, 145, 146, 152, 161, 162, 167, 170, 173, 175, 178, 179, 184, 189, 194, 195, 200, 203, 207, 208, 215, 216, 221, 222, 228, 229, 230, 242, 249, 251, 253, 254, 258, 266, 267, 269, 270, 275, 286, 290, 293, 294, 295, 299, 300, 308, 313, 314, 315, 317, 320, 324, 329, 330, 333, 345, 356, 361, 362, 365, 369, 374, 375, 377, 383, 389, 400, 403, 404, 405, 410, 414, 418, 420, 428, 432, 439, 440, 443, 448, 452, 453, 454, 455, 476, 483, 485, 488, 492, 505, 509, 518, 519, 534, 538, 540, 545, 548, 550, 551, 566, 572, 575, 578, 579, 585, 599, 605, 608, 614, 620, 623, 638, 639, 641, 648, 657, 662, 663, 671, 674, 683, 685, 689, 698, 706, 713, 723, 725, 730, 734, 735, 744, 753, 764, 767, 768, 785, 790, 804, 830, 833, 845, 850, 854, 855, 859, 869, 878, 888, 896, 905, 910, 918, 920, 923, 924, 929, 944, 960, 963, 964, 968, 969, 986, 988, 995, 1001, 1004, 1016, 1031, 1033, 1049, 1055, 1088, 1104, 1115, 1118, 1163, 1168, 1175, 1180, 1193, 1208, 1235, 1238, 1251, 1262, 1269, 1273, 1274, 1283, 1300, 1301, 1303, 1307, 1320, 1329, 1340, 1343, 1349, 1350, 1364, 1383, 1394, 1395, 1397, 1400, 1403, 1439, 1440, 1473, 1478, 1490, 1493, 1496, 1499, 1505, 1509, 1518, 1520, 1538, 1539, 1543, 1548, 1554, 1580, 1581, 1610, 1614, 1615, 1619, 1620, 1628, 1640, 1645, 1678, 1692, 1700, 1724, 1733, 1748, 1763, 1765, 1790, 1797, 1805, 1819, 1838, 1863, 1868, 1886, 1895, 1904, 1940, 1945, 1970, 1977, 1991, 2000, 2013, 2015, 2024, 2025, 2054, 2065, 2078, 2079, 2090, 2093, 2105, 2130, 2138, 2143, 2144, 2153, 2183, 2224, 2228, 2230, 2238, 2245, 2246, 2255, 2315, 2333, 2355, 2366, 2373, 2390, 2408, 2438, 2493, 2504, 2508, 2528, 2533, 2544, 2573, 2610, 2615, 2624, 2636, 2654, 2673, 2687, 2693, 2705, 2750, 2760, 2783, 2786, 2813, 2814, 2888, 2915, 2973, 2984, 3014, 3035, 3039, 3074, 3083, 3089, 3128, 3158, 3177, 3219, 3258, 3275, 3293, 3305, 3363, 3368, 3380, 3386, 3390, 3403, 3425, 3479, 3506, 3533, 3599, 3608, 3616, 3620, 3650, 3719, 3725, 3740, 3770, 3773, 3815, 3850, 3855, 3905, 3953, 3974, 3989, 4003, 4043, 4067, 4070, 4088, 4128, 4148, 4155, 4178, 4199, 4239, 4250, 4262, 4301, 4310, 4328, 4370, 4454, 4469, 4488, 4495, 4533, 4568, 4583, 4640, 4660, 4670, 4673, 4703, 4805, 4860, 4968, 5090, 5105, 5183, 5228, 5288, 5339, 5360, 5375, 5387, 5445, 5485, 5523, 5528, 5585, 5651, 5774, 5849, 5885, 5888, 5903, 5951, 6004, 6035, 6081, 6140, 6173, 6224, 6234, 6344, 6380, 6383, 6389, 6449, 6515, 6525, 6548, 6554, 6590, 6605, 6613, 6635, 6675, 6998, 7065, 7160, 7175, 7241, 7298, 7343, 7360, 7370, 7395, 7481, 7560, 7565, 7778, 7820, 7835, 7898, 8036, 8060, 8120, 8180, 8183, 8258, 8289, 8303, 8483, 8595, 8853, 9095, 9104, 9110, 9149, 9158, 9218, 9243, 9293, 9329, 9395, 9458, 9575, 9815, 9843, 9848, 9860, 9908, 10004, 10060, 10095, 10205, 10436, 10485, 10523, 10913, 11058, 11165, 11297, 11339, 11400, 11480, 11493, 11645, 11948, 11960, 12048, 12113, 12195, 12353, 12548, 12668, 12950, 13110, 13148, 13388, 13448, 13920, 13938, 14108, 14348, 14795, 14945, 15167, 15191, 15803, 16115, 16433, 16508, 16610, 16965, 17000, 17025, 17135, 17603, 17933, 17963, 18323, 18821, 18968, 19268, 19280, 19478, 19520, 19763, 20463, 20570, 21335, 21398, 21635, 22028, 22100, 22280, 22760, 22880, 23939, 24011, 24170, 24350, 24585, 24695, 25340, 25695, 25892, 26270, 26753, 26990, 29733, 30743, 31394, 31568, 32075, 32915, 32975, 34085, 35783, 35883, 36230, 36908, 37244, 38390, 40388, 41105, 43755, 44195, 51623, 52550, 55658, 61403, 62168, 64413, 78585, 109250, 146858]
for f in five:
DP[f] = 5
for f in four:
DP[f] = 4
N = int(input())
print(DP[N] if bool(DP[N]) else 3)회고
이런식의 문제를 처음 봐서 상당히 당황했고, 답을 찾지 못했다.
새로운 유형임을 알았고, 다음에는 풀이할 수 있도록 해보겠다.
PS린이