728x90
https://www.acmicpc.net/problem/17626
17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
n = int(input())
result = [0, 1]
for i in range(2, n+1):
min_value = 1e9
j = 1
while (j ** 2) <= i:
min_value = min(min_value, result[i - (j ** 2)])
j += 1
result.append(min_value + 1)
print(result[n])n = int(input())
result = [0] * (n + 1)
result[0] = 0
result[1] = 1
for i in range(2, n+1):
min_value = 1e9
j = 1
while (j ** 2) <= i:
min_value = min(min_value, result[i - (j ** 2)])
j += 1
result[i] = min_value + 1
print(result[n])
dp.. 어렵다..
반응형
'전.py' 카테고리의 다른 글
| [python] 백준 1166 선물 (0) | 2022.02.15 |
|---|---|
| [python] 프로그래머스 주차 요금 계산 (Lv.2) (0) | 2022.02.15 |
| [python] 백준 1764 듣보잡 (0) | 2022.02.14 |
| [python] 백준 1676 팩토리얼 0의 개수 (0) | 2022.02.14 |
| [python] 백준 11723 집합 (0) | 2022.02.14 |
