[종만북] 크리스마스 인형

AC 코드입니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
 
 
int waysToBuy(const vector<int>& psum, int k) {
    const int MOD = 20091101;
    int ret = 0;
    vector<long long> count(k, 0); //overflow를 방지
    for (int i = 0; i < psum.size(); i++) {
        count[psum[i]]++;
    }
    for (int i = 0; i < k; i++) {
        if (count[i] >= 2) {
            ret = (ret + ((count[i] * (count[i] - 1)) / 2)) % MOD;
        }
    }
    return ret;
}
 
int maxBuys(const vector<int>& psum, int k) {
    //ret[i] : 첫 번째 상자부터 i번째 상자까지 고려했을 때 살 수 있는 최대 횟수
    vector<int> ret(psum.size(), 0);
    //prev[s] = psum[]이 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()
{
    int c;
    scanf("%d", &c);
    while (c--) {
        int n, k;
        scanf("%d %d", &n, &k);
        vector<int> psum(n + 1);
        psum[0] = 0;
        for (int i = 1; i <= n; i++) { //input + 부분 합 구하기
            int temp; scanf("%d", &temp);
            if (i == 1) psum[1] = temp % k;
            else psum[i] = (psum[i - 1] + temp % k) % k;
        }
        //case 1
        printf("%d ", waysToBuy(psum, k));
        //case 2
        printf("%d\n", maxBuys(psum, k));
    }
}

 

부분합 문제입니다.

 

이 문제는 두 가지를 출력해야 한다.

 

• 한 번 주문할 때 가능한 주문 방법의 수
• 여러 번 주문할 때 주문이 겹치지 않게 최대 몇 번 주문할 수 있는가?

 

1. 한 번 주문할 때 가능한 주문 방법의 수(waysToBuy)

 

문제에서 가능한 주문의 경우는 H번부터 T번까지의 부분합이 k로 나누어질 때를 말한다.

 

따라서 이 문제에서 부분합은 k로 나눈 나머지를 의미한다.

따라서 부분합 배열(psum)을 모두 k로 나눈 나머지로 정의한 후 

psum에서 중복된 값들의 횟수를 모두 count배열에 저장해둔다.

 

이때 주문할 수 있는 방법의 수는 psum에서 같은 값들 중 2개를 뽑는 수와 같다.(nC2 조합)

 

이게 가능한 이유는 만약 psum [a] = psum [b]이라면, 이 둘을 빼면 반드시 0이 나오며

이는 즉 a~b-1 을 모두 더한 값이 k로 나누어진다는 것을 의미한다.

(모든 psum 의 값은 k로 나눈 나머지를 의미하기 때문이다)

 

여기서 주의해야할 점은 psum을 구할 때 psum [1]이 첫 번째 상자값이고

psum [0]은 존재하지 않는 값이기 때문에 미리 0으로 선언해두어야 한다는 점이다.

 

0번째 인덱스 값을 구해놓는 이유는

• 처음에 psum 배열을 초기화할 때 그 전 psum 값이 필요하기 때문에
• 조합의 수를 구할 때 첫번째 상자부터 주문하는 경우를 세어주기 위해서

이처럼 두가지 이유가 있다.

 

 

2. 여러 번 주문하는 경우, 주문이 겹치지 않는 최대 주문 수(maxBuys)

 

이 경우 부분합을 이용한 dp의 형태로 풀 수 있다.

dp [i] : 0 ~ i번 상자의 범위 내에서 서로 겹치지 않고 구매할 수 있는 부분 구간의 최대 수

로 두고, 두 가지 경우로 나누어 보자

 

• i번 상자를 고르지 않는 경우 : i번 상자를 제외하고, 나머지 상자들에 대해 재귀 호출을 이용하면 당연하게도 dp [i-1]과 동일한 값이 나온다.
• i번 상자를 고른 경우 : psum[i] = psum [j-1]인 j를 찾고, dp [j]+1을 해주면 된다. 이 경우 j의 값이 여러 개일 수 있지만, 가장 높은 값을 구하기 위해선 가장 i와 가까운 j을 찾고 리턴해주면 되겠다.

두 번째 경우 j의 값을 빠르게 구하려면, dp 배열을 만드는 과정에서 psum의 값이 나오면, 그 값의 인덱스를 저장해두는 배열(prev)을 하나 만들어두면 된다.

 

이 배열을 만들게되면 i번 째 상자를 고를 때 동일한 값의 인덱스를 O(1) 시간에 구할 수 있다.