수들의 합 5 ( 2018 번 )

2018번: 수들의 합 5

 

---

🧠 알고리즘

• 투 포인터(Two Pointers)

 

✔️ 동작 방식

[ 핵심 아이디어 ]

• 연속된 자연수의 합은 왼쪽 ~ 오른쪽 까지 구간 합으로 표현할 수 있다
• 합(num)이 N보다 작으면 → 오른쪽 확장, N보다 크거나 같으면 → 왼쪽 축소

[ 로직 요약 ]

1. l, r는 연속된 자연수 구간의 시작과 끝 포인터
2. num은 현재 구간의 합
3. r > N이 되면 더 이상 합이 커질 수 없으므로 종료
4. 누적된 answer가 정답

---

 

🧾 코드

import sys

def _main():
    answer = 0
    l, r, num = 1, 1, 0

    while l <= r:
        if num < n:
            if r > n:
                break
            num += r
            r += 1
        elif num >= n:
            if num == n:
                answer += 1
            num -= l
            l += 1
            
    return answer
    

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

---

 

⏱️ 시간 복잡도

while l <= r : 각 포인터는 최대 N까지 한 번씩만 이동 ( 선형 시간 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )