[백준] 1484번 다이어트 - Python

이번에 해결해 볼 문제는 백준에 있는 1484번 다이어트입니다.

---

문제 설명

• (성원이의 현재 몸무게) ** 2 - (성원이가 생각하는 자신의 몸무게) ** 2이 G라고 했을 때 성원이의 현재 몸무게로 가능한 몸무게를 구하는 문제입니다.

문제 해결 아이디어

• 우선 몸무게를 하나씩 탐색해야하므로 two-point 알고리즘이 효율적이지 않을까 생각했습니다.
• Two-point 알고리즘을 사용하기 위해서는 시작점(start)과 끝점(end)의 기준점이 필요합니다.
  • start와 end를 모두 1로 두고 한다면 시간이 많이 소비됩니다.
  • 그래서 저는 start가 1일 때 가능한 end의 최대를 찾았습니다.
  • end = int(G**0.5) + 1
• 이제는 문제 조건에 해당하는 start와 end를 찾기 위해 two-point 알고리즘의 핵심인 루프를 수행하게 될텐데 이때 루프를 종료할 조건을 설정해줘야 합니다.
  • 🤔 해당 문제를 해결하면서 가장 고민을 많이 했던 부분인 것 같습니다.
  • 우선 start가 end를 넘으면 안되기 때문에 start < end라는 조건은 필수적입니다. 왜냐하면 G의 값은 항상 자연수이기 때문에 성원이가 생각한 자신의 몸무게가 성원이의 현재 몸무게를 넘어갈 수 없기 때문입니다.
  • 추가적으로 다른 조건이 있는지 생각을 해봤지만 위의 조건만 만족한다면 문제를 해결할 수 있으므로 더 이상의 조건 추가는 하지 않았습니다.

문제 해결 코드

import sys

input = sys.stdin.readline

G = int(input())

start = 1
end = int(G**0.5) + 1
result = []

while start < end:
    val = end**2 - start**2

    if val == G:
        result.append(end)
        start += 1
        end += 1
    elif val < G:
        end += 1
    else:
        start += 1

if result:
    for r in result:
        print(r)
else:
    print(-1)