문제 설명

제곱수의 합

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	68235	28119	20530	40.315%

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

접근 방법

1. 일단 dp[i] 정의 = i를 제곱수의 합으로 표현할 때의 최소 항 개수
2. min_count를 만든다

코드

N = int(input())
dp = [0] * (N+1)

for i in range(1,N+1):
	min_count = i 
	j = 1 
	while j*j <= i : 
		dp[i] = min(min_count,dp[i-j*j]+1]
		j += 1 
	dp[i] = min_count
	
print(dp[N])

(선택사항) 오류 해결

원래는 이걸 min_count를 i로 할 생각을 못했ㅇ듬…

뭔가 나한테는 아직 dp가 무조건 피보나치같은 애들로 생각이 되나봄.

→ DP는 피보나치처럼 단순한 연속 관계일 때도 있지만 / 모든 가능한 선택지들을 확인하면서 최소값(또는 최대값)을 고르는 문제