본문 바로가기
알고리즘

[백준 2559] 알고리즘 109일차 : 수열

by SiO2whocode 2021. 7. 26.
반응형

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

 

2559번: 수열

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기

www.acmicpc.net

C++ 투포인터

구간의 정해진 크기만큼의 합이 최대인 값을 구하는 문제

 

접근방법

구간이 정해져있어서 s와 e를 한번에 한칸씩 오른쪽으로 옮기면서 최대합을 갱신하면 된다.

처음에 시작할때 s = 0 , e = k-1 구간의 합을 구해서 sum의 초기값으로 대입한다.

그 후에 e가 n-1보다 작을때까지 반복문을 돌면서 최대합 갱신

while문을 나올때 e = n-1 이어야 배열의 마지막 원소인 arr[n-1]까지 포함한 것이므로

 

소스코드

#include <iostream>
using namespace std;

int main(){
    //init & input
    int n, k;
    cin >> n >> k;
    
    int tempr[n];
    for(int i = 0 ; i < n ; i++){
        cin >> tempr[i];
    }
    
    int s,e;
    s = e = 0;
    int max, sum = 0;
    
    //process
    sum = tempr[s];
    while(e < k-1){
        sum += tempr[++e];
    }
    
    max = sum;
    
    while(e < n-1){
        sum -= tempr[s++];
        sum += tempr[++e];
        max = ( sum > max ? sum : max );
    }
    
    //output
    cout << max <<"\n";
    
    return 0;
}

 

반응형

댓글0