다이어트 ( 1484 번 )

1484번: 다이어트

 

---

🧠 알고리즘

• 투 포인터

 

✔️ 동작 방식

 

• 두 변수 now(현재 몸무게 후보), prev(기억 몸무게 후보)를 1에서 시작.
• 반복하면서 now² - prev² 값을 계산.
  • == n이면 정답 후보에 now 추가.
  • < n이면 차이를 키우기 위해 now += 1.
  • > n이면 차이를 줄이기 위해 prev += 1.
• now가 100000을 넘어가면 종료.
• 정답 후보가 없으면 -1, 있으면 오름차순으로 출력.

---

 

 

🧾 코드

import sys

def _main(n):
    answer = []
    now, prev = 1, 1
    
    while now < 100001:
        now_cr = (now ** 2) - (prev ** 2)
        if now_cr <= n:
            if now_cr == n:
                answer.append(now)
            now += 1
        else:
            prev += 1

    if answer:
        return "\n".join(map(str, answer))
    return -1

n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

while now < 100001 : 100001 까지 고정길이 반복 ( 상수 시간 )

해당 알고리즘 시간 복잡도 : 상수 시간 복잡도 ( O(1) )