1699

날짜 : 2023. 03. 18

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10**6)

n = int(sys.stdin.readline())
dp = [0] * 100001

dp[1] = 1
dp[2] = 2
dp[3] = 3
i = 1
while (i * i) < 100001:
    dp[i*i] = 1  # 제곱수는 무조건 1
    i += 1


def fun(idx):
    t = int(idx ** 0.5)  # 최대 제곱근
    dp[idx] = idx
    for i in range(t, 1, -1):
        dp[idx] = min(dp[idx], dp[i ** 2] + dp[idx - i ** 2])
    return


for i in range(1, n + 1):
    if dp[i] == 0: fun(i)  # 제곱수가 아닌 경우 함수 실행

"""print()
for i in range(1, n + 1):
    print(i, dp[i])"""
print(dp[n])

 

 

풀이

- 1부터 (n + 1)까지의 dp를 구한 후 해당 값을 출력한다.

 

 

알게된 점

- n에 대해 최대 제곱수가 아닌 모든 제곱수에 대해서 생각해 보아야 풀리는 문제였다.

 

* 반례 : 18의 경우 9 + 9 -> 2 // 12의 경우 4 + 4 + 4 -> 3 이라는 값이 도출된다.

- 해당 케이스에서 최대 제곱수를 적용한다면 각각16 + 1 + 1 : 3 // 9 + 1 + 1 + 1 : 4 => 최소값 도출이 불가능

 

 

 

참고 사이트

-