[BOJ] 1484 - 다이어트

문제 출처

백준 1484 - 다이어트

 

풀이

엔토피아가가 선물해준 저울로 젠 G 킬로그램이 주어지면 성원이의 현재 몸무게로 가능한 것을 모두 구하는 문제였습니다.

 

G 킬로그램 = {성원이의 현재 몸무게}² - {성원이가 기억하고 있던 몸무게}²

 

G는 100,000 보다 작거나 같기 때문에 무작정 큰 수까지 돌려서 제곱 - 제곱의 조합을 찾기에는 시간초과가 날 것입니다.

 

그래서 어떤 상한선이 있을 것이라 생각했고 수가 커질수록 제곱 - 제곱의 결과가 커진다는 것을 알아내어 제곱 - 제곱의 결과가 G보다 커지는 경우 더이상 몸무게를 찾지 않도록 해주었습니다.

 

코드

small-j/BOJ_Algorithm