백준 1229 <육각수> Python

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

---

DP 를 사용해 풀 수 있습니다.

우선 N 보다 작은 육각수를 모두 구해줍니다.

육각수는 N x (2N - 1) (N >= 1) 의 규칙을 띄고 있으니 반복문을 통해 구해줄 수 있습니다.

 

육각수의 최소 개수를 알고 싶은 타겟 i 보다 작은 육각수들을 순회하며

memo[i - 육각수] + 1 의 개수들을 비교해 최솟값을 기록하면 됩니다.

+ 1 은 육각수를 하나 고르면 해당 육각수 1 개를 더해주는 것입니다.

---

import sys

from bisect import bisect_left

input = sys.stdin.readline

def solution(N):

    # N 보다 작은 육각수 리스트

    hex_list = [0]

    # 카운트

    i = 1

    j = 1

    while True:

        # N 이하면

        if i*j <= N:

            hex_list.append((i)*(j))

            i += 1

            j += 2

        # 크면 끝

        else:

            break

    # DP / memo[i] = i 를 만드는데 필요한 육각수의 최소 개수

    memo = [0]

    # 순회

    for i in range(1, N+1):

        # 1(i 이하인 육각수) + (i - (i 이하인 육각수)를 만드는데 필요한 육각수의 최소 개수))

        # 중 가장 작은값 찾기

        min_hex_cnt = float('inf')

        for j in range(1, len(hex_list)):

            # i 보다 크면 끝

            if hex_list[j] > i:

                break

            # 최솟값 최신화

            min_hex_cnt = min(min_hex_cnt, 1 + memo[i-hex_list[j]])

        # memo 최신화

        memo.append(min_hex_cnt)

    return memo[-1]

   

# 입력

N = int(input().strip())

print(solution(N))