[부분 합] CHRISTMAS 크리스마스 인형

1. 크리스마스 인형

 

이 문제는 두가지의 문제를 풀어야한다.

 

선물상자의 인덱스 0~n

 

주문한번:  a번 박스 부터 b번 박스까지 구매 

 

1. 산타가 아이들에게 같은양의 선물을 주고 남은 나머지가 0인 상자의 구간의 개수

2. 산타가 아이들에게 띄엄 띄엄 주문해서(중복x) 주문한번당 아이들에게 나머지 없이 나누어주는

    최대의 주문 수

 

 

2. 1번 문제

 

1번문제에서 이 문제는 부분 구간의 부분합을 구해야한다는 것을 알 수 있다.

 

psum[a] = 0~a 까지의 합 

order(a, b) = a 에서 b까지 주문하고 총 인형의 개수 라고 하자.

 

아이들한테 남는거 없이 선물하므로,

 

order(a, b) % child == 0 이 되어야함을 알 수 있다.

 

order(a, b) = psum[b] - psum[a-1]

 

order(a, b) % child = psum[b]%child - psum[a-1]%child   = > 0

 

따라서 이 문제는 다음과 같이 psum만 구하면 쉽게 답을 얻을 수 있다.

 

psum[b]%child = psum[a-1]%child 

 

이것은 O(n)의 시간복잡도가 걸린다.

 

간단하게 다음과 같이 메모이제이션을 하면 된다.

 

cache[remainder] = psum[] 을 child로 남은 나머지인 remainder를 가지는 상자의 개수.

 

그리고 이 배열을 다시 탐색하면서 (cache[r])(cache[r]-1)/2을 구해 전부 더하면 된다.

 

3. 2번 문제

 

이 문제는 그리드 알고리즘으로 풀린다.

 

중복되지 않으므로 앞에서 부터 상자들을 탐색하면서 psum의 나머지를 구하고

 

1번문제처럼 cache[psum[]%child]에 1씩 더해간다.

 

만약 psum의 나머지가 같은 것이 이전에 한번 나왔으면 그것을 선택한다.

(그 이전것과 연결하여 주문할 시 가장 짧은 구간이 된다,)

 

 

여기서 중요한것은 가장 최근에 나머지가 같은 상자의

인덱스를 따로 기억할 필요가 있다는것이다.

 

인덱스를 메모이제이션하지 않고 푸는 방법도 있다.

선택하고 다음에 cache[]를 반복문으로 탐색하며 0으로 초기화한다.

이는 중복되게 주문을 못하기 때문에 가능하다.

(cache를 bool 변수로 구현해도 상관없다, 한번 나왔으면 true)

 

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
 
using namespace std;
 
int dollBoxN;
int childN;
int box[100000];
const int MOD = 20091101;
int psum[100000];
 
pair<int,int> pcache[100000];
int cache[100000];
 
int partialMemo()
{
    int oneCount = 0;
   
    psum[0] = box[0]%childN;
   
    for(int i = 0; i < dollBoxN; i++)
    {
        cache[i] = -1;
        if(i!=0)psum[i] = (psum[i-1] + box[i]%childN)%childN;
        if(pcache[psum[i]].second != 0)
        {
            cache[i] = pcache[psum[i]].first;
            oneCount= (oneCount + (pcache[psum[i]].second)%MOD)%MOD;
        }
        if(psum[i] == 0) 
        {
            if(cache[i]==-1)
                cache[i] = 0;
            oneCount = (oneCount + 1)%MOD;
        }
        pcache[psum[i]].first = i;
        pcache[psum[i]].second++;
    }
    return oneCount%MOD;
}
int greedy()
{
    int count = 0;
    // first ~ second 
    pair<int, int> top(-1, -1);
    for(int i = 0; i < dollBoxN; i++)
    {
        if(cache[i] == -1) continue;
 
        if(cache[i] >= top.second) 
        {
            top.first = cache[i];
            top.second = i;
            count++;
        }
    }
    return count;
}
 
int main()
{
    int T;
    cin>>T;
    for(int i = 0; i < T; i++)
    {
        for(int i = 0; i < 100000; i++)
        {
            pcache[i].first = -1;
            pcache[i].second = 0;
        }
 
        cin>>dollBoxN;
        cin>>childN;
        for(int j = 0; j < dollBoxN; j++)
        {
            scanf("%d",&box[j]);
        }
        printf("%d ",partialMemo());
        printf("%d\n",greedy());
    }
}