[백준 1699번] 제곱수의 합

문제 보기

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

1699번: 제곱수의 합

 

문제 해결

dp 문제는 규칙성을 찾는 것이 중요하다.

제곱수의 최대 항의 개수는 1을 제외한 완전제곱수(4,9,16..)를 고려하지 않을 때의 값이므로

1은 1개, 2는 2개, 3은 3개, 4는 4개... 인덱스만큼의 개수를 가지게 된다.

 

그리고 수가 증가하는 반복문을 돌텐데 자기보다 작거나 같은 수에서 완전제곱수를 만나게 되면

개수는 1로 초기화된다.

이 규칙을 생각해내야 문제를 해결할 수 있다.

 

소스 코드

import sys
input = sys.stdin.readline

n = int(input())

# 제곱수를 생각하지 않을 때, 최대 항의 개수는 1^2씩 더하는 것이므로
dp = [i for i in range(n+1)]

for i in range(1, n+1):
    for j in range(1, i):
        if j*j > i:
            break
        if dp[i] > dp[i-j*j] + 1:
            dp[i] = dp[i-j*j] + 1

print(dp[n])

 

참고 자료

https://jyeonnyang2.tistory.com/50