[2435번] 기상청 인턴 신현수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 슬라이딩 윈도우

슬라이딩 윈도우 기법을 이용하는 방식이다.

슬라이딩 윈도우는 크기를 고정시켜 값을 비교해나가는 과정으로 이 문제는 매우 기본적인 문제중 하나이다.

슬라이딩 윈도우는 덱으로 풀어도 되고, 그냥 변수를 이용하여 자신이 원하는대로 풀어도된다.

덱 없이 푼 코드에 슬라이딩 윈도우가 어떻게 동작하는지 상세한 주석을 달아놓았다.

소스 코드 : 

(덱을 이용하여 푼 코드)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#include <iostream> #include <cstdio> #include <deque>   #define max(a,b)(a > b ? a : b)   using namespace std;   int main() {     int n, m;     int arr[101];       scanf("%d %d", &n, &m);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       int sum = 0;     int val = 0;       deque<int> dq;       while (dq.size() < m)     {         int t = dq.size();         sum += arr[t];         dq.push_back(arr[t]);     }       val = sum;          for (int i = m; i < n; i++)     {         sum -= dq.front();         dq.pop_front();                  dq.push_back(arr[i]);         sum += arr[i];                  val = max(val, sum);     }       printf("%d", val);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

(덱 없이 푼 코드)

#include <iostream>
#include <cstdio>
#include <deque>
 
#define max(a,b)(a > b ? a : b)
 
using namespace std;
 
int main()
{
    int n, m;
    int arr[101];
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    int sum = 0;
    int val = 0;
 
    // 첫 범위에 해당하는 값만큼 sum에 +
    for(int t = 0; t < m; t ++)
        sum += arr[t];
 
    // 최댓값은 처음 sum값으로 초기화
    val = sum;
 
    // 앞에값은 빼주고, 뒤에값은 더해주는 방식으로 크기 유지
    for (int i = m; i < n; i++)
    {
        sum -= arr[i-m] + arr[i];
        sum += arr[i];
        
        val = max(val, sum);
    }
 
    printf("%d", val);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>