ALGOSPOT CHRISTMAS 알고스팟 크리스마스 인형

ALGOSPOT CHRISTMAS 알고스팟 크리스마스 인형

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include <algorithm>
#include<cmath>
using namespace std;
 
int n, k;
 
//D[]의 부분 합 배열 psum[]과 k가 주어질 때, 몇 가지 방법으로 살 수 있는지 반환한다.
//psum[]의 첫번째 원소 전에 0을 삽입했다고 가정한다.
int waysToBuy(const vector<int> &psum, int k) {
    const int MOD = 20091101;
    int ret = 0;
    //psum[]의 각 값을 몇 번이나 본 적 있는지 기록한다.
    vector<long long> count(k, 0);
    for (int i = 0; i < psum.size(); i++)
        count[psum[i]]++;
    //두 번 이상 본 적 있다면 이 값 중 두 개를 선택하는 방법의 수를 더한다.
    //순열과 조합 nC2 공식 적용
    for (int i = 0; i < k; i++)
        if (count[i] >= 2)
            ret = (ret + ((count[i] * (count[i] - 1)) / 2)) % MOD;
    return ret;
}
//D[]의 부분 합 배열 psum[]과 k가 주어질 때,겹치지 않게 몇 번이나 살 수 있는지 반환한다.
//psum[]의 첫 번째 원소 전에 0을 삽입했다고 가정한다.
int maxBuys(const vector<int>& psum, int k) {
    //ret[i]=첫 번째 상자부터 i번째 상자까지 고려했을 때 살 수 있는 최대 횟수
    vector<int> ret(psum.size(), 0);
    //prev[s]=psump[]이 s였던 마지막 위치
    vector<int> prev(k, -1);
    for (int i = 0; i < psum.size(); i++) {
        //i번째 상자를 아예 고려하지 않는 경우
        if (i > 0)
            ret[i] = ret[i - 1];
        else
            ret[i] = 0;
        //psum[i]를 전에도 본 적이 있으면,prev[psum[i]]+1부터 여기까지 쭉 사 본다.
        int loc = prev[psum[i]];
        if (loc != -1) ret[i] = max(ret[i], ret[loc] + 1);
        //prev[]에 현재 위치를 기록한다.
        prev[psum[i]] = i;
    }
    return ret.back();
}
 
 
 
int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int cases;
    cin >> cases;
    while (cases--) {
        cin >> n >> k;
        vector<int> v(n);
        for (int i = 0; i < n; i++)
            cin >> v[i];
        vector<int> psum(n + 1);
        psum[0] = 0;
        for (int i = 1; i <= n; i++)
            psum[i] = (psum[i - 1] + v[i - 1]) % k;
        
        cout << waysToBuy(psum, k) << " " << maxBuys(psum, k) << endl;
    }
 
}

문제출처:https://algospot.com/judge/problem/read/CHRISTMAS

부분합,동적계획법을 사용한 문제입니다. 순열과 조합의 공식도 사용해서 

한번 주문할 수 있다면,가능한 주문 방법은 몇 가지인지 쉽게 풀 수 있는 방법이 있네요.