[백준]_2018번_수들의 합 5[C++]

문제

 

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

32 MB

10151

4683

3589

48.956%

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

예제 입력 1

15

예제 출력 1

4

 

---

시간 복잡도 분석으로 사용할 알고리즘의 범위 부터 줄여야 한다.

 

문제에서 주어진 시간제한은 2초

N의 최댓값은 10,000,000으로 매우 크게 잡혀 있다.

O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 것 ⇒ 투 포인터

 

(연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현하자. ‘시작 인덱스’ ‘ 종료 인덱스’를 투포인터로 지정 후 접근

---

Sudo code

N(연속된 자연수의 합)
start_index = 1;
end_index = 1;
sum = 1; //현재 연속된 합 값을 저장하는 변수

while(end_index != N) {
		if(sum == N) 경우의 수 증가, end_index 증가, sum값 변경
		else if(sum > N) sum값 변경, start_index증가
		else if(sum < N) end_index 증가, sum 값 변경
}
경우의 수 출력

 

---

풀이

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false); // 입력과 출력 속도 향상을 위한 코드
    cin.tie(NULL); // cin과 cout이 묶여 있는 버퍼를 풀어주는 코드
    cout.tie(NULL);

    int N;
    cin >> N; // 입력받을 수 N

    int count{ 1 }, start_index{ 1 }, end_index{ 1 }, sum{ 1 };
    // count : 연속된 수열의 갯수
    // start_index : 현재 수열의 첫 번째 인덱스
    // end_index : 현재 수열의 마지막 인덱스
    // sum : 현재 수열의 합. 처음 수열은 {1}이므로 sum도 1로 초기화

    while (end_index != N) {
        if (sum == N) { // 현재 수열의 합이 N과 같으면
            count++; // 연속된 수열의 갯수를 1 증가시키고
            end_index++; // 현재 수열의 마지막 인덱스를 1 증가시키고
            sum = sum + end_index; // sum도 갱신한다.
        }
        else if (sum > N) { // 현재 수열의 합이 N보다 크면
            sum = sum - start_index; // 현재 수열의 첫 번째 인덱스를 하나 증가시키면서 합에서도 빼준다.
            start_index++; // 첫 번째 인덱스를 1 증가시킨다.
        }
        else { // 현재 수열의 합이 N보다 작으면
            end_index++; // 현재 수열의 마지막 인덱스를 1 증가시키면서
            sum = sum + end_index; // 합도 갱신한다.
        }
    }
    cout << count << "\\n"; // 연속된 수열의 갯수 출력
    return 0;
}

1. 프로그램이 시작되고 입력 값 N을 초기화합니다.
2. 변수 count, start_index, end_index 및 sum이 선언되고 초기화됩니다.
3. end_index가 N이 될 때까지 while 루프가 실행됩니다.
4. 루프의 각 반복에서 프로그램은 현재 합계가 N과 같은지 확인합니다. 일치하면 count 변수가 증가하고 end_index 및 sum 변수가 업데이트됩니다.
5. 현재 합계가 N보다 큰 경우 프로그램은 합계에서 start_index의 값을 빼고 start_index를 증가시킵니다.
6. 현재 합계가 N보다 작으면 프로그램은 end_index를 증가시키고 end_index의 값을 합계에 추가합니다.
7. end_index가 N이 되면 while 루프가 중지되고 프로그램이 count 값을 출력합니다.