백준 1484 다이어트 (파이썬)

문제 : https://www.acmicpc.net/problem/1484

 

정답 코드

import sys

def solve():
    curWeight = 1
    memoWeight = 1
    answer = []
    if G < 3:
        print(-1)
        return
    while True:
        powDiff = curWeight ** 2 - memoWeight ** 2
        diff = curWeight - memoWeight
        # 몸무게 차이가 1이하 이면서 G보다 크면 종료
        if powDiff > G:
            if diff == 1:
                break
            memoWeight += 1

        elif powDiff == G:
            answer.append(curWeight)
            memoWeight += 1

        elif powDiff < G:
            curWeight += 1

    if answer:
        for i in answer:
            print(i)
    else:
        print(-1)
    return

if __name__=="__main__":
    input = sys.stdin.readline
    G = int(input().strip())
    solve()

 

결과 및 정리

현재 무게^2 - 기억 무게^2를 순서쌍으로 나타내면 (2,1) (3,1) (3,2) (4,1), (4,2), (4,3) ,,, 로 나타낼 수 있습니다.

먼저 G가 최소 3 이상은 되어야 자연수 범위에서 계산이 가능하기 때문에 G가 3 미만인 경우를 예외 처리했습니다.  

제곱의 차와 G 의 대소 관계를 투 포인터를 옮겼습니다.

 

1. 먼저 제곱의 차가 G보다 큰 경우, 기억하고 있는 무게를 증가시켰습니다. 그런데 두 몸무게의 차이가 1인 경우는 그 후에도 값이 G 보다 커지기만 해서 종료를 시켰습니다.

 

2. 그 다음 제곱의 차가 G랑 같은 경우, 출력 리스트에 추가시켰습니다.

 

3. 제곱의 차가 G보다 작은 경우, 현재 몸무게를 증가시켜 차이를 벌려주었습니다

 

따로 수열이나 숫자가 정해지지 않았지만 이는 곧 수열이 없어도 풀 수있다는 의미이고 가상의 끝없는 자연수 수열에서 투 포인터를 사용한다고 생각하면 될 것 같습니다.