https://www.acmicpc.net/problem/1699
1699번: 제곱수의 합어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다www.acmicpc.net
의외로 정말 어려웠던 문제였다.
푼 방법
먼저, n까지의 제곱수를 구현해 놓는다.
그다음 n까지의 리스트를 선언한다.
반복문을 통해 리스트를 돌면서,
만일 i가 제곱수이면, 값에 1을 넣는다.
만일 i가 제곱수가 아니면, i보다 작은 모든 제곱수에 대하여
(i-제곱수) + 1 을 구하고, ## 제곱수j에서 i를 만드는 최솟값 + 제곱수는 항상 1
이중 min값을 구한다.
이후 리스트의 n 번째 원소를 출력한다.
n=int(input())squared_num=[x*x for x in range(1, int(n**0.5)+1)] #제곱수들
l=[x for x in range(n+1)] #입력값들for i in range(1,len(l)): min_list=[i]
for j in squared_num: if i<j: break if i==j:
min_list.append(1) break
min_list.append(1+l[i-j]) l[i]=min(min_list) print(l[n])추가로 더 깔끔한 코드
n=int(input())d=[0]*(n+1)d[1]=1for i in range(2,n+1): d[i]=d[i-1]+1
index=2 l=[d[i]] while True:
under = i-(index*index) ## i와 제곱수의 차이 if under<0:
break
## d[under은] 제곱수와의 차잇값을 만들수있는 최소갯수
# 제곱수는 항상 1번이면 만드므로 1더해주기
l.append(d[under]+1) index+=1 #다음 제곱수 d[i]=min(l)print(d[n])파이썬에서 풀면 시간을 엄청나게 잡아먹고,
파이파이에서풀면 메모리를 엄청나게 잡아먹는다.