[백준 BOJ] 2018번 수들의 합 5 (C++/cpp)

문제 설명

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

2018번: 수들의 합 5

 

접근 방법 - 두 포인터의 기본 문제

백준의 2018번 문제는 두 포인터 알고리즘을 사용하여 해결해야 하는 기초 문제이다.

해당 문제는, 연속된 숫자들의 합이 입력값인 경우의 수가 얼마인지를 구하여 출력해야 하는 문제이다.

여기서 두 포인터란, 진짜 포인터를 사용하는 것이 아니라, 2개의 변수로 배열의 인덱스를 가리키며 해결하는 원리를 뜻한다.

이에 비슷한 원리로 되어있는 문제에 대하여 이전에 작성한 ps 글이 있는데, 이 링크를 아래에 기재해놓았다.

이 알고리즘을 처음 접해본다면, 아래의 글도 함께 참고해보길 바란다.

https://smary-it.tistory.com/225

[백준 BOJ] 11728번 배열 합치기 (C++/cpp)

보통 시간 초과를 피하기 위해 사용하는 알고리즘이기 때문에 이를 꼭 유의하자.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 값(n)을 입력받는다.

 

2) 연속된 숫자의 범위를 조절하기 위해, start 변수와 end 변수를 각각 선언한다.

- start는 범위의 시작을 나타내기 때문에, 1로 초기화하였다.

- end는 범위의 끝을 나타내기 때문에, 현재 start 값 다음인 2로 초기화하였다.

 

3) 경우의 수를 측정하기 위한 변수 cnt를 0으로 초기화하여 선언한다.

 

4) start와 end로 이루어진 범위가 유효할 때까지, 반복문을 실행하여 아래의 연산을 취한다.

- 지정된 범위의 총합을 저장할 변수 sum을 0으로 초기화하여 선언한다.

- 지정된 범위의 숫자들을 순차적으로 sum에 더한다.

- 만약 sum 값이 n과 동일하다면, 이는 경우의 수에 포함되기 때문에 cnt에 1을 더하도록 한다. 그리고 다음 범위를 탐색하기 위해 start에 1을 더한다.

만약 sum이 n보다 크다면, 범위를 줄여 sum을 작게 할 필요가 있다. 따라서 이 경우엔, start에 1을 더한다.

만약 sum이 n보다 작다면, 범위를 늘려 sum을 크게 할 필요가 있다. 따라서 이 경우엔, end에 1을 더한다.

 

5) 위 연산이 완료되었다면, 최종적으로 저장된 cnt를 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 2018번 코드
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int n;
    cin >> n;
    
    int start = 1;
    int end = 2;
    int cnt = 0;
    while (end - start > 0) {
        int sum = 0;
        for (int i = start; i < end; i++) { sum += i; }
        if (sum == n) { 
            cnt++; start++; 
        }
        else if (sum > n) { start++; }
        else { end++; }
    }
    cout << cnt << endl;
}

 

제출 결과

(2022.08.28 백준 2018번 문제 제출 결과)

시간초과 극혐