DP...

#1699번 https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

n = int(input())
dp = [x for x in range(n+1)]
# 각각의 인덱스 = 수, 값 = 수(인덱스)를 구하는데 들어가는 제곱수의 합의 최소 갯수
# 일단은 1을 가지고 더했을 경우로 초기화

for i in range(1, n+1): # 1부터 제곱수의 합을 차근차근 구해줌 : DP.
    for j in range(1, i):  # 목표 수 보다 작은 값들로 루프
        if j**2 > i:       # j값의 제곱이 목표 수보다 커질 경우에 루프 종료 -> 효율성
            break
        if dp[i] > dp[i - j**2] + 1:  # 이 전에 구한 값을 사용해줘야함 : DP의 핵심기능
            dp[i] = dp[i - j**2] + 1  # 특정한 제곱수를 빼 줬을 경우에 나오는 수의 제곱수의 합에 1을 더해줌 -> 현재 수의 제곱수의 합.
                                      # 이렇게 루프를 돌면서 모든 값을 처리 -> 최솟갑 저장

print(dp[n])

이번 문제도 쉽진 않았다.

처음에는 가능한 제곱수 중 제일 큰 수부터 진행했ㄴ었는데

틀렸다.

 

역시나..

 

그래서 또 검색.. 또 이해.. 적용.. 정답...

 

아... 언제쯤 알고리즘을 잘 풀 수 있을까..

 

아무튼 내용은 이렇다.

각 index를 구하는 제곱수의 합의 수의 갯수를 value에 저장한다.

초기값 설정은 모든 수(index)를 1로 더해서 구할 경우로 설정한다. 

작은 수 부터 구하기 시작한다. (Bottom Up)

i값보다 작은 수의 제곱수의합은 이미 구해져 있으니 이들의 합으로 구성된다.