문제 출처 : www.acmicpc.net/problem/17626
17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
문제 해석 : 모든 수는 4개 이하의 제곱 수로 나타 낼 수 있다. 이때 주어진 N은 최소 몇개의 제곱수로 나타낼 수 있는가?
문제 풀이 : DP 문제로 풀이 할 수 있다. 자신의 수에서 그보다 작은 수의 제곱수를 뺀 것의 최소를 구하고 거기에 한개를 더해주면 된다.
가능한 다른 풀이 : 브루트포스로 가능한 모든 경우를 풀어 볼 수도 있다.
풀이 코드
N = int(input())
dp = [0,1]
for i in range(2, N+1):
min_value = 1e9
j = 1
while (j**2) <= i:
min_value = min(min_value, dp[i - (j**2)])
j += 1
dp.append(min_value + 1)
print(dp[N])author : donghak park
contact : donghark03@naver.com
## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.
'📊알고리즘, 문제풀이 > 📈문제풀이 (PS)' 카테고리의 다른 글
| [알고리즘][Python] 백준 1149 RGB 거리 문제 풀이 (0) | 2021.01.17 |
|---|---|
| [알고리즘][Python] 백준 18870 좌표 압축 문제 풀이 (0) | 2021.01.15 |
| [알고리즘][Python] 백준 17219 비밀번호 찾기 문제 풀이 (3) | 2021.01.15 |
| [알고리즘][Python] 백준 11727 2xN 타일링 2 문제 풀이 (0) | 2021.01.15 |
| [알고리즘][Python] 백준 11726 2xN 타일링 문제 풀이 (0) | 2021.01.15 |