Hacker Earth) Winter is coming 문제

https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/winter-is-coming-12/description/

1 ≤ Elements of array ≤ 10⁹
1 ≤ T ≤ 10
1 ≤ N ≤ 100000

여러 테스트케이스에 대해 

배열의 크기 N 이 주어지고 N개의 원소가 입력으로 들어온다.

각각의 배열의 원소는 1~10억이다.

연속된 부분 배열들 중 부분 배열의 원소의 합이 N으로 나누어 떨어지는 부분배열의

왼쪽과 오른쪽 인덱스를 구하는 문제이다(인덱스는 1부터 시작)

만약 답이 여러개라면 가장 작은 길이의 배열을, 그래도 여러개라면 가장 왼쪽에 있는 배열을 출력한다.

우선 답이 없는 경우는 없다 왜냐하면 배열의 원소가 N 개 이기때문에 최악의 경우는 답이 '1 N' 일 것이다.

이 문제는 굳이 말하자면 그리디, 누적합, math 라고 할 수 있겠다.

우선 부분합을 다 구하자. 그런데 실제 합은 알 필요가 없고 나머지만 있으면 된다.

그 이유는 우선 부분배열 = pSum[r] - pSum[l] 인데 부분배열이 N으로 나누어 떨어지기

위해선 pSum[r] % N 과 pSum[l] % N 이 같으면 된다.

그런데 여기서 중요한건 최적의 답을 구하기 위해서는 길이가 최소가 되어야 하기때문에

지금까지 본 누적합 pSum 중 N으로 나눈 나머지가 0~N-1 인 가장 나중 인덱스를 갱신을 해놓아야 한다. 왜냐하면 가장 짧은 부분 배열을 요구하기 때문에 가장 나중 인덱스를 가지고 있어야 길이가 짧아 지기 때문이다. 

다만 하나의 예외 처리가 필요하다 N으로 나눈나머지가 같은 누적합이 앞에서 아직 한번도 안나왔다면 지금 보고있는 누적합을 N으로 나눈 나머지가 0일 때만 답을 업데이트 해주고 1~N-1 일때는 업데이트 해주면 안된다 왜냐하면 빼서 나머지가 0이 될 수 없기때문이다. 

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
int left[100003];
int T,N;
int A[100003];
ll pSum[100003];
int main() {
    inp1(T);
    while(T--){
        memset(left,0,sizeof(left));
        memset(pSum,0,sizeof(pSum));
        inp1(N);
        FOR(i,N) inp1(A[i]),pSum[i+1]=pSum[i]+A[i];
        int l=0,r=INF;
        REP(i,1,N){
            int updL=-1;
            int mod = pSum[i]%N;
            if(mod) {
                if(left[mod]) updL = left[mod];
            }
            else updL = left[mod];
            if(updL != -1 && r-l > i-updL) l = updL, r = i;
            left[mod]=i;
        }
        printf("%d %d\n",l+1,r);
    }
 
    return 0;
}