BOJ 1484번: 다이어트

www.acmicpc.net/problem/1484

1484번: 다이어트

아이디어:

G = 현재 몸무게^2 - 기억하던 몸무게^2

현재 몸무게와 기억하던 몸무게가 뭐든 될 수 있으니까..(이게 무슨..) 자연수의 제곱 중에서 투포인트를 사용해서 차가 G가 되는 경우를 구하자.

일단 가능한 몸무게의 배열을 만들고 (1~200000까지의 제곱) result, left, right 모두 0으로 초기화한다.

result가 g보다 큰 경우 left++, 작은 경우 right++

 

import sys
g = int(sys.stdin.readline())

arr = []
for i in range(1, 200001):
    arr.append(i**2)
    
left, right = 0, 0
ans = []
result = 0

while(True):
    #탈출 조건 주의
    if (right==200000): break
    
    result = arr[right] - arr[left]

    if (result>g):
        left+=1
        
    else:
        if (result==g):
            ans.append(right+1)
        right+=1
        
if (len(ans)==0):
    print(-1)
else:
    for i in ans:
        print(i)

※ 탈출 조건 주의!

※ 자연수를 넣을 때 너무 작은 수를 넣어서 틀렸다. 200000 정도는 넣어야 하나보다.