백준 11974 Subsequences Summing to Sevens (USACO January 2016 Silver 2번)

문제 링크: https://www.acmicpc.net/problem/11974

11974번: Subsequences Summing to Sevens

Prefix Sum

문제 예시를 보면, 3 5 1 6 2 14 10이라는 7개의 숫자가 있고, pSum % 7을 구해보면 3, 1, 2, 1, 3, 3, 6 이 됨.

1이라는 나머지가 처음 나오는 위치는 두번째고, 마지막에 나오는 위치는 네 번째인데, 그 말은 세 번째에서 네 번째 숫자까지 2개의 숫자의 합이 7의 배수임을 뜻함.

3이라는 나머지가 처음 나오는 위치는 첫번째고, 마지막에 나오는 위치는 여섯 번째인데, 그 말은 첫 번째에서 여섯 번째 숫자까지 5개의 숫자의 합이 7의 배수임을 뜻함.

#include <bits/stdc++.h>
using namespace std;
 
int n, pSum, idx[7][2];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int num;
        cin >> num;
 
        pSum += num;
        pSum %= 7;
        if(pSum == 0) idx[0][1] = i;
        else {
            if(idx[pSum][0] == 0) idx[pSum][0] = i;
            else idx[pSum][1] = i;
        }
    }
 
    int ans = 0;
    for(int i = 0; i < 7; i++)
        ans = max(ans, idx[i][1] - idx[i][0]);
 
    cout << ans << '\n';
    return 0;
}