[baekjoon] 백준 1699번(파이썬): 제곱수의 합

문제

1699번: 제곱수의 합

알고리즘

- 각 자연수를 만드는 제곱수에 최대 항의 개수를 dp에 저장한다.

- 이중 반복문을 통해 각 자연수를 만드는 제곱수에 항의 개수를 구한다.

- 각 자연수가 제곱수보다 작다면 제곱수로 항의 개수를 만들지 못하므로 반복을 멈춘다.

- 각 자연수를 만다는 제곱수에 최소 항의 개수를 구한다.

코드

pypy3 해결

# pypy3 (통과)
# python3 (시간초과)
import sys

n = int(sys.stdin.readline())
dp = [x for x in range(100001)] # 각 자연수를 만드는 제곱수에 최대 항의 개수

# 반복문을 통해 각 자연수를 확인
for i in range(1, n + 1):
    # 반복문을 통해 각 자연수를 만드는 제곱수에 항의 개수를 구한다.
    for j in range(1, i):

        # 각 자연수가 제곱수보다 작다면 제곱수로 항의 개수를 만들지 못하므로 반복을 멈춘다.
        if i < j * j:
            break

        # 각 자연수를 만드는 제곱수에 최소 항의 개수를 구한다.
        dp[i] = min(dp[i], dp[i - j * j] + 1)

print(dp[n])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법