[python] 1699 제곱수의 합 (미해결)

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

 

 

 

고민:

입력한 수를 num이라 하자

sqrt(num)값이 가장 큰 제곱수일 것이다

그 수를 제외한 나머지의 sqrt()값이 가장 크다

계속 반복해서 1일 때까지 개수를 세본다

또, cnt 변수도 쓰겠다

 

## 오답

# 입력, 기본 설정
import math
num = int(input())
cnt = 0
tot = num

# 제곱수 항의 최소 개수 구하기
while(tot!=0):
    #print(tot) #
    sqrtNum = int(math.sqrt(tot))
    tot -= sqrtNum * sqrtNum
    cnt += 1

# 출력
print(cnt)

반례 -> 18 = 3^2+ 3^2 = 4^2 + 1^2 + 1^2

최소항의 개수는 2인데 3으로 나옴

 

내가 처음 생각한 답은 단순하게 제곱하는 수가 크면 좋은 건줄 알았다(그리디 알고리즘)

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/#:~:text=Greedy%EB%8A%94%20'%ED%83%90%EC%9A%95%EC%8A%A4%EB%9F%AC%EC%9A%B4%2C%20%EC%9A%95%EC%8B%AC,%EB%90%98%EB%8A%94%20%EA%B7%BC%EC%82%AC%EC%A0%81%EC%9D%B8%20%EB%B0%A9%EB%B2%95%EC%9D%B4%EB%8B%A4. 

 

 

 

<동적 계획법, Dynamic Programming>

모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘

그리디 알고리즘에 비해 시간이 오래 걸리지만, 항상 최적의 해를 구할 수 있다.

 

 

 

 

교훈:

1. while(조건문) 실수 주의

여기 안에는 특정 경우의 반대로 써야함

tot==0 까지 반복한다 -> tot !=0

2. ??

https://chanhuiseok.github.io/posts/baek-10/

설명을 봐도 이해가 잘 안감