문제

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

풀이(분석)

풀이 1

N은 1 ~ 10만
K는 1 ~ 10만 포함(1과 N 사이 값)
온도는 -100 ~ 100

연속된 온도의 합이 '최대'가 되는 값 : 구간합 prefix sum
psum[i] = psum[i - 1] + a[i]; ➡️ 누적합 활용!!

💡 Tip

문제에서 최대값을 구하라고 하면 최소값부터 최대값을 구하라는 의미이다.
반대로, 최소값을 구하라고 하면 최대값부터 최소값을 구하라는 의미이다.

• 최대값 구하는 로직
  ret = max(ret, value);

ret에다가 최대값을 계속 갱신해나가면서 최종적인 최대값 만들어서 반환한다.

• 최소값 구하는 로직
  ret = min(ret, value);

이 문제의 최소값은?
-100이 10만번 나온다고 하자. >> 어림잡아 -1000만이라고 볼 수 있다. 그러나 -1000만보다 조금 더 여유롭게 잡아주는 게 좋다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k, temp, psum[100001], ret = -10000004;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) {
    	cin >> temp;
        psum[i] = psum[i - 1] + temp;
    }
    
    for (int i = 1; i <= n; i++) {
    	ret = max(ret, psum[i] - psum[i-k]);
    }
    cout << ret << "\n";
    return 0;
}

풀이 2

접근 사고를 다양하게 하기 위해 다른 풀이도 가져와서 분석해보았다.

// 다른 풀이
#include<bits/stdc++.h> 
using namespace std;  
  
int findMaxTemptrue(const int *arr, const int &N, const int &K) {
  int first = 0;
  int last = K;
  int maxSum = 0;
  int savedSum = 0;

  for (int i = 0; i < K; i++) {
    maxSum += arr[i];
    savedSum += arr[i];
  }

  while(last < N) {
    int curSum = savedSum - arr[first] + arr[last];
    savedSum = curSum;

    if (curSum > maxSum)
      maxSum = curSum;

    first++;
    last++;
  }
  return maxSum;
}

int main() {
  int N, K;
  cin >> N >> K;

  int *arr = new int[N];

  for (int i = 0; i < N; i++) {
    cin >> arr[i];
  }

  cout << findMaxTemptrue(arr, N, K) << "\n";

  return 0;
}

이건 투포인터 알고리즘이라는데 아직은 모르겠다 ...

이해하려고 했던 나름의 고군분투. 뇌가 굳은 느낌

개선

누적합 개념을 잘 익혀두자.
일단 기본적인 템플릿은 외워둬야 함.