[백준] 2018번 : 수들의 합 5

---

🔗 문제 링크

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

👩‍💻 코드

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    int start_index = 1;
    int end_index = 1;
    int sum = 1;
    int count = 1;
    
    cin >> N;
    
    while(end_index != N){
        if (sum == N){
            count++;
            end_index++;
            sum += end_index;
        } else if (sum > N){
            sum -= start_index;
            start_index++;
        } else {
            end_index++;
            sum += end_index;
        }
    }
    
    cout << count << "\n";
}

✏️ 풀이

Do it! 알고리즘 코딩테스트 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.

이 책에서 투 포인터라는 알고리즘을 도입하여 문제 풀이를 하였습니다.

이 알고리즘은 O(n)의 시간 복잡도로 굉장히 빠른 속도로 정답을 도출 할 수 있습니다.

 

우선 자기 자신(N)은 정답에 미리 추가하여 count = 1로 시작합니다.

자연수의 합이므로 index에서 0도 고려하지 않고 1부터 시작합니다.

 

핵심 알고리즘은 start_index와 end_index, 두 포인터를 사용하는 것입니다.

먼저 연속된 숫자의 합(sum)이 N과 같거나 커질 때까지 end_index를 증가시킵니다.

1 +2, 1+2+3, 1+2+3+4, 1+2+3+4+5...

 

연속된 숫자의 합이 N과 같다면 정답 횟수가 추가되며 end_index를 한 칸 뒤로 밉니다.

1+2+3+4+5 -> 1+2+3+4+5+6

sum : 15 -> 21, 즉 sum += end_index 

 

연속된 숫자의 합이 N보다 크다면 start_index를 한 칸 뒤로 밉니다.

1+2+3+4+5+6 -> 2+3+4+5+6

sum : 21 -> 20, 즉 sum -= start_index

 

연속된 숫자의 합이 N보다 작아도 N과 같을 때와 똑같이 end_index를 한 칸 뒤로 밉니다.

하지만 이 경우에는 정답 횟수가 추가되지 않습니다.

5+6 -> 5+6+7

sum : 11 -> 18, 즉 sum += end_index