백준 알고리즘 - 제곱수의 합 (1699) [Python]

 문제

 

www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

 

 

 

 

 문제 상황

 

- 입력받은 정수 N을 자연수의 제곱수의 합으로 표현할 때 최소 항의 개수를 출력한다.

 

 

 

 

 

 해결 전략

 

- 처음엔 brute force식으로 생각했지만 이렇게는 해결 불가능하다. N보다 작은 최대의 제곱수를 제거하며 계산하려고 햇지만 반례가 생길 수 있다. N을 만드는 방법은 결국 부분적으로 쪼갤 수 있는데 이 쪼개는 기준이 중요하다. 

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N = int(input())
cache = [0]*(N+1) # N을 만드는데 필요한 최소 제곱수의 개수 
for i in range(N+1):
    cache[i] = i # 1로만 표현하는 경우
    for j in range(1,i): # sqrt로 생각하지말고 역으로 제곱으로 접근하면 된다.
        if j*j > i: break
        if cache[i] > cache[i-j*j]+1: cache[i] = cache[i-j*j]+1
print(cache[N])

 

 

 

 

 

 해설

 

- 작은 수 부터 저장해나가기 때문에 제곱수를 1부터 올려가며 계산해도 된다. 즉, 같은 제곱수가 2개 이상이더라도 이미 제곱수 하나를 뺀 값의 결과물에 그 제곱수의 값이 저장되있으므로 하나만 관찰하며 쌓아나가도 무방하다.

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 백준 알고리즘 사이트는 너무나 속도에 민감해서 2개의 값을 min하는 것 조차 속도 이슈가 생겼다. 단순히 2항이라 2의 연산 속도만 추가될 뿐인데 if문으로 변경해 해결하였다.