[Algospot] 알고스팟 크리스마스 인형 문제풀이(CHRISTMAS)

문제 핵심 1번은 부분합, 2번은 동적 계획법

1. Psum[T] = Psum[H-1]임을 이용, count변수를 통해 각 Psum값이 몇 번 나오는지 저장, 각 count값 중 2 이상인 것들에 대해 2개 무작위로 뽑는 경우의 수의 합이 한 번 주문하는 방법 수와 같음

2. [0]~[i]번까지 주문할 때 최대 주문 수 -> [0]~[i-1]까지 주문하는 경우에서 [i]상자를 구매하는 경우와 안하는 경우를 비교 / 구매하는 경우에는 Psum값이 같은 곳 중 최근에 본 위치를 알고있어야 하므로, prev[Psum[i]]를 사용.

 

#include<iostream>
#include<vector>
#include<algorithm>
#define MOD 20091101
using namespace std;
 
/*
K명에게 인형을 사주는데,
N개의 인형상자가 한 줄로 진열되어있음
각 상자에 1개 이상의 인형이 있음
각 상자에 번호가 있고, 주문형태는 H번부터 T번 상자까지(H<=T)
 
한번 주문 시마다 각 상자 인형 꺼내서 각각 K명에게 분배하고, 남는 인형이없도록 함
    1. 한 번 주문할 수 있다면, 가능한 주문 방법 수는?
    2. 여러 번 주문할 수 있다면, 주문이 안겹치게 최대 몇번 주문가능?
    (주문이 겹침 = 두 주문에 같은 번호의 인형상자 포함)
 
 
<입력>
T(테스트케이스, <=60)
N K(둘다 1~10만)
1~N번 상자까지 각 인형상자에 들어있는 인형개수 Di
(i는 1~N, Di는 1~10만)
 
<출력>
1번답, 2번답을 한 줄에 하나의 빈칸으로 나누어 출력
(1번답은 % 20091101 계산해서 출력)
 
*/
 
int Psum[100001];    //Psum[i] : 0번부터~(i-1)번 상자까지의 인형 합 % K
int N, K;
 
int oneTake() {    //한 번 주문 가능한 모든 경우의 수
    //(a, b)가 주문가능하려면, (Psum[b] - Psum[a-1]) % K = 0 즉, Psum[b] % K = Psum[a-1] % K이어야 한다는 뜻
    //즉, Psum값이 서로 같은 두 인덱스값을 뽑으면 그게 하나의 경우이므로
    //각 Psum값이 몇개나오는지 카운트하는 변수 vector<int> count(K, 0); 을 만들어야 함
    //count[i] = Psum[x]=i인 x의 개수
    //-> count를 뒤져보며, 값이 2 이상인 값 x에 대해 모두 xC2를 계산해서 더하면 됨(x개 중 2개를 임의로 뽑는 경우의 수)
    vector<long long> count(K, 0);
 
    for (int i = 0; i <= N; i++) {
        count[Psum[i]]++;
    }
    long long int res = 0;    //결과값
    for (int i = 0; i < K; i++) {
        if (count[i] >= 2) {
            res += (count[i] * (count[i] - 1) / 2) % MOD;
        }
    }
    return res % MOD;
}
 
 
int manyTake() {    //[0]~[a]까지에서 여러번 살 수 있을 때 안겹치는 최대 구매횟수
    vector<int> prev(K, -1);    //prev[i] : Psum에서 가장 마지막에 i 값을 본 인덱스위치 저장
    vector<int> DP(N+1, 0);        //DP[i] : [0]~[i-1]까지 가장 많이 구매하는 경우의 수
    DP[0] = 0;
 
    for (int i = 0; i <= N; i++) {
        if (i > 0) DP[i] = DP[i - 1];
        int location = prev[Psum[i]];    //이전 위치
        if (location != -1) {    //이전 위치에서 구매 가능한 경우를 찾은 경우 -> 해당 위치에서 구매할 경우와 그렇지 않은 경우 비교해서 DP에 저장
            DP[i] = max(DP[i], DP[location] + 1);
        }
        //위치 기록
        prev[Psum[i]] = i;    
    }
    return DP.back();
}
 
 
int main() {
    int T; cin >> T;
    while (T--) {    //testcase
        cin >> N >> K;    //상자 수, 사람 수
 
        for (int i = 0; i < 100000; i++) {
            Psum[i] = 0;
        }
 
        vector<int> box(N + 1);    //각 상자(인형 수 저장)
        Psum[0] = 0;
        for (int i = 1; i <= N; i++) {
            int a; cin >> a; box[i - 1] = a;
            Psum[i] = (Psum[i - 1] + box[i - 1]) % K;
        }    //Psum 입력 완료
 
        cout << oneTake() << " ";
        cout << manyTake() << endl;
 
    }
    return 0;
}