Search

[백준 1699] 제곱수의 합

[백준 1699] 제곱수의 합

Tip

자연수 값 그대로 DP 테이블 초기화
반복문을 통해 각각의 자연수가 특정 제곱수보다 작은지 판별
작으면 break를 통해 반복문 탈출
같거나 크다면, d[i] 값이 제곱수를 빼고 1을 더한 값보다 큰지 판별
크다면 d[i] 값은 1을 더한 값으로 초기화

풀이 소스 코드

import sys si = sys.stdin.readline # n 입력 n = int(si()) d = [i for i in range (n + 1)] for i in range(1, n + 1): for j in range(1, i): if j * j > i: break if d[i - j * j] + 1 < d[i]: d[i] = d[i - j * j] + 1 print(d[n])
Python