[백준] 17262. Four Squares - Python
17262. Four Squares
https://www.acmicpc.net/problem/17626
DP - 성공
from sys import stdin
import math
N = int(stdin.readline())
dp = [0]*(N+1)
for i in range(1, N+1):
tmp = int(math.sqrt(i))
m = 4
for j in range(tmp, 0, -1):
m = min(m, dp[i-j*j] + 1)
dp[i] = m
print(dp[N])1 ~ N 까지의 숫자들마다 최소 개수의 제곱수 합을 구해줘서 dp 에 저장
이 때, 최대 4 개의 제곱수로 이루어지기 때문에 최대 개수 m 은 4 로 초기화
각 숫자들의 루트 값부터 1 까지 (역순으로) 조합들을 모두 확인해서 최솟값을 찾아준다
Author And Source
이 문제에 관하여([백준] 17262. Four Squares - Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsh5408/백준-17262.-Four-Squares-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
