[백준 BOJ] 2559번 수열 (C++/cpp)

문제 설명

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

2559번: 수열

 

접근 방법 - 두 포인터의 응용문제

백준의 2559번 문제는 두 포인터의 원리를 이용하여 해결해야 하는 문제이다.

해당 문제는, 입력받은 수열에 대하여 정해진 크기의 특정 연속된 구간의 합이 가장 큰 경우를 찾아 출력해야 하는 문제이다.

우선 설명하기에 앞서, 필자는 두 포인터의 개념만 알고 기술하는 내용들임을 미리 밝히고자 한다.

구간의 크기가 입력값으로 정해지며 그중 최댓값만 알아내면 되는 것이기 때문에, 이 알고리즘에 어느 정도 익숙하다면 어렵지 않게 풀 수 있을 것으로 예상된다.

필자의 경우엔, 입력과 합 연산을 동시에 수행하면서 실행 시간을 줄여보도록 하였다.

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

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

 

 코드의 실행 순서

1) 수열을 입력받을 배열(arr)을 전역 변수로 선언해둔다.

 

2) 수열의 길이(n)와 구간의 크기(k)를 입력받는다.

 

3) 구간의 합에 대한 최댓값을 저장할 변수 max를, 임의의 작은 수로 초기화하여 선언한다.

(입력값 범위를 보면, 수열값들 중 음수도 있기 때문에 반드시 절댓값이 큰 음수로 지정해야 한다.)

마찬가지로, 구간의 합 연산에 이용할 변수 sum을 0으로 초기화하여 선언한다.

 

4) 구간의 시작을 나타내는 변수 start를 0으로 초기화하여 선언한다.

 

5) 구간의 끝을 나타내는 변수 end를 0으로 초기화하여 선언하는데, 이 변수를 반복문의 제어 변수로 사용하면서 아래의 연산을 취하도록 한다.

- arr의 값을 하나씩 입력받는다. 여기서, 인덱스는 end로 갖는다.

- 인덱스를 현재 end로 갖는 arr 값을 sum에 더하도록 한다.

- 만일 end가 k보다 크거나 같다면, 이 경우는 end가 앞으로 나아가면서 start도 그에 따라 함께 움직여야 함을 뜻한다.

따라서 이 경우엔, sum에서 start를 인덱스로 갖는 arr의 값을 빼고 start의 값을 1 증가한다.

- 만일 start-end 구간이 k 크기인 상태에서의 sum 값이 max보다 크다면, max를 해당 sum의 값으로 갱신한다.

 

6) 모든 연산이 완료되었다면, 최종적으로 연산된 max의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

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

//백준 2559번 코드
int arr[100001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int n, k;
    cin >> n >> k;

    int max = -100000;
    int sum = 0;
    int start = 0;
    for (int end = 0; end < n; end++) {
        cin >> arr[end];
        sum += arr[end];
        if (end - k >= 0) {
            sum -= arr[start];
            start++;
        }
        if (end + 1 >= k && sum > max) {
            max = sum;
        }
    }

    cout << max << endl;
}

 

제출 결과

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