• 문제 : https://www.acmicpc.net/problem/2559

1. 문제 접근

• 1. 누적합을 통한 prefix sum 배열로 해결해야 함

---

2. 시행착오

• 코드 자체는 맞긴 했지만, 누적합 배열을 활용해서 더 깔끔하게 짤 수 있던 점을 간과
  • 누적합 배열을 사용하지 않고, 원본 값들을 배열에 그대로 저장하고 presum이라는 변수에 저장하고 값을 갱신하는 방법을 썼음

---

3. 코드 및 풀이

3.1 첫 번째 풀이

#include <bits/stdc++.h>
using namespace std;

int n, k;
int arr[100004];
int presum, ret;

int main(){

    // 1. Input n, k and each temperature for n
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    // 2. sum for arr[0] ~ arr[k-1]
    for(int i = 0; i <= k-1; i++){
        presum += arr[i];
    }

    ret = presum;

    // 3. sum
    for(int i = k; i < n; i++){
        presum = presum - arr[i-k] + arr[i];
        if(presum > ret) ret = presum;
    }

    cout << ret;
    return 0;
}

3.2 두 번째 풀이(advance)

1.psum이라는 누적합 배열을 사용
2. ret이라는 초기 값을 설정함 : 초기값을 100000 x -100(N의 최대 범위 x 온도 최소값) => 10,000,000 + 4(값 오버플로우 방지용)
3.누적합은 첫 번재 index부터 사용해야 함 => 0번째 Index는 항상 0이어서, 반복문을 더할 때 이상업게끔
4.max()를 활용해 조건문 없애기
5.psum[i] - psum[i-k]을 활용 : i번째 누적합에서 i-k누적합을 빼면 자연스럽게 i+1 ~ i까지의 합이 구해짐

• ex)
  k = 3
  원본 수 : 1, 2, 3, 4, 5
  누적합배열 : 0, 1, 3, 6, 10, 15
  i= 4일때의 누적합 = psum[4] = psum[1] = 10-1 : 9
  => 즉 2+3+4의 합을 구한 것이랑 동일한 연산
  

#include <bits/stdc++.h>
using namespace std;

int n, k, temp, psum[100001];
int ret = -10000004;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 1. input and make presum
    cin >> n >> k;

    for(int i = 1; i <= n; i++){
        cin >> temp;
        psum[i] = psum[i - 1] + temp;
    }

    // 2. calculate max value;
    for(int i = k; i <= n; i++){
        ret = max(ret, psum[i] - psum[i-k]);
    }

    cout << ret;
    
    return 0;
}

---

Reference