python 2018 수들의 합 5

📌 문제 정보

• 문제 번호: 2018
• 문제: https://www.acmicpc.net/problem/2018
• 난이도: 실버 5

---

🧩 문제 요약

자연수 N이 주어졌을 때, 연속된 자연수들의 합으로 N을 나타낼 수 있는 경우의 수를 구하는 문제.
(단, 수는 하나 이상 이어져야 함)

---

🧪 예제 입력 / 출력

예제 입력 

15

 

 

예제 출력 

4

 

 

설명: 15를 만들 수 있는 경우의 수는 다음과 같음

• 1 + 2 + 3 + 4 + 5
• 4 + 5 + 6
• 7 + 8
• 15 (자기 자신)

총 4가지 경우

---

💡 접근 방식

처음엔 완전탐색이 떠오르지만, 시간 초과 방지를 위해 투 포인터 방식으로 접근하는 것이 적절함.
자연수의 연속된 합이라는 성질을 이용하면, 1부터 시작해서 수를 더해가며 조건을 만족하는지 확인 가능함.

---

⚙️ 알고리즘 설명

• 두 개의 포인터 (start_index, end_index)를 1로 초기화
• 현재까지의 합(sum)을 1로 설정하고,
• 합이 N보다 작으면 end_index를 증가시키고 합에 더함
• 합이 N보다 크면 start_index를 증가시키고 합에서 빼줌
• 합이 정확히 N이면 경우의 수(cnt) 증가
• 이 과정을 end_index == N이 될 때까지 반복

---

🧑‍💻 코드 구현 (Python)

 

import sys

input = sys.stdin.readline

N = int(input())
sum = 1
cnt = 1  # 자기 자신 하나만으로 표현 가능한 경우 포함
start_index = 1
end_index = 1

while end_index != N:
    if sum > N:
        sum -= start_index
        start_index += 1
    elif sum < N:
        end_index += 1
        sum += end_index
    else:  # sum == N
        cnt += 1
        end_index += 1
        sum += end_index

print(cnt)

---

🔁 다른 풀이 / 코드 개선 방향

• 다른 접근 방식으로는 수학적 공식을 이용해 시간 복잡도를 더 줄일 수 있음
• 예: 두 수 i, j에 대해 합이 (i + j) * (j - i + 1) / 2가 N인지 확인
• 하지만 투 포인터 방식이 직관적이고 구현이 쉬움

---

⏱️ 시간복잡도 분석

• 시간 복잡도: O(N)
  • 각 포인터는 최대 N까지 이동함
• 공간 복잡도: O(1)
  • 별도의 배열이나 리스트를 사용하지 않음

---

📝 결론 및 팁

• 연속된 수의 합 문제는 투 포인터로 자주 출제됨
• 자기 자신을 포함하는 경우도 꼭 고려할 것
• 유사한 접근 방식이 필요한 문제를 함께 풀어보는 것을 추천

유사 문제 추천

• 2003번 수들의 합 2: https://www.acmicpc.net/problem/2003
• 10986번 나머지 합: https://www.acmicpc.net/problem/10986