https://www.acmicpc.net/problem/1699
시간 2초, 메모리 128MB
input :
- N (1 ≤ N ≤ 100,000)
output :
- 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력
조건 :
- 예를 들어 11=3^2+1^2+1^2(3개 항)이다.
- 11의 경우 11=2^2+2^2+1^2+1^2+1^2(5개 항)도 가능하다.
- 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
어렵다.. 어려워..
맨 처음엔 그냥 가장 큰 제곱수 빼다 보면 나오지 않을 까 해서 data리스트에 제곱수를 다 만들어서 빼게 시켰다. 그러나 틀리고,
가장 큰 제곱수만 뺀 다고 되는게 아니라.
현재 숫자 i
i 보다 작은 제곱수들의 리스트 s.
이 작은 제곱 수들을 num 이라 할 떄.
i - num 의 숫자에 num을 더해서 i로 만들어 줄 것 이기 때문에.
i가 만들어 지는 경우는 dp[num] + i 라고 할 수 있다.
만들어 질 때도 항의 개수가 가장 작아야 하기 때문에 num들이 들어 있는 s를 (dp[num]들이 들어 있게 해서 가장 min값을 찾은 후에 dp[i] + 1 해주자.
현재 만들어야 할 수가 5라면
1에서 4를 더할지, 4에서 1을 더할지 생각해야 되고.
현재 만들어야 할 수가 10이라면
9에서 1을 더할지,
6에서 4를 더할지,
1에서 9를 더할지,
dp[9] / dp[6] / dp[1]의 값들 중 최솟값에 1을 더하는(숫자 1개를 더한다.) 계산을 해 주자.
import sys
N = int(sys.stdin.readline())
data = [i * i for i in range(1, 320)]
dp = [0 for i in range(N + 1)]
for i in range(1, N + 1):
s = []
for j in data:
if j > i:
break
s.append(dp[i - j])
dp[i] = min(s) + 1
print(dp[N])
