문제 출처

1. 문제설명

  • 블로그를 시작하고 지난 일수 N,
  • 계산을 원하는 일수 X가 주어진다.
  • X일 동안 방문한 최대 방문자를 구하라.
    • 단, 0이 아니라면 기간이 몇 개인지 출력하라.



2. 알고리즘 설계

  • 누적합 알고리즘을 사용한다.
    • 누적합의 원리
      • [1,2,3,4,5]가 있다고 해보자
      • 누적합 배열은 [1,3,6,10,15]가 된다.
        • 각 원소를 지날 때마다 그 이전 값을 전부 더해주는 방식이다.
        • 그렇다면, 3~5까지 총 3개의 누적합은 어떻게 구하면 될까?
          • 5의 자리는 15이고, 2의 자리는 3이다.
          • 이 두 개의 값을 빼주면 3~5의 누적합이 계산된다.
      • 즉, 구하고자 하는 마지막 구간의 누적합에서 처음 구간 - 1의 누적합을 빼주면 된다!
  • 1번 예제를 예시로 들어보겠다.
    • [1, 4, 2, 5, 1]이 입력이고, 2일 동안 최대 방문자를 구하는 것이다.
    • 2+5=7이 2일간의 최대값이고, 합이 7이 되는 값은 하나밖에 없다.
    • 따라서, 7과 1이 나오게 된다.



3. 로직

  • 누적합 중 최대값을 갱신해주고,
    • 갱신될 때는 cnt는 1이 된다.
    • 새로운 값이 발견 됐으니, 무조건 1이다.
  • 만약 현재 최대값과 같다면 cnt++



4. 전체 코드

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

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, x;
	cin >> n >> x;

	vector<int> v(n + 1);
	vector<int> dp(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		dp[i] = (i > 0) ? dp[i - 1] + v[i] : v[i];
	}

	int res = 0, cnt = 0;
	for (int i = x; i <= n; i++) {
		int prefix_sum = dp[i] - dp[i - x];

		if (res < prefix_sum) {
			res = prefix_sum;
			cnt = 1;
		}
		else if (res == prefix_sum) cnt++;
	}

	if (res == 0) cout << "SAD";
	else cout << res << '\n' << cnt;

	return 0;
}