[Algospot] 크리스마스 인형 (문제 ID : CHRISTMAS)

문제

크리스마스를 맞이하여 산타 할아버지는 전세계의 착한 어린이 K명에게 인형을 사주려고 한다. 산타 할아버지는 인형을 구입하기 위해서 유명한 인형가게인 "놀이터"에 찾아갔다. 놀이터에는 N개의 인형 상자가 한 줄로 진열되어 있고, 각 인형 상자에는 한 개 이상의 인형이 들어 있다. 그리고 놀이터에서는 주문의 편의성을 위해 각 상자에 번호를 붙여 놓았고, 주문은 "H번 상자부터 T번 상자까지 다 주세요."라고만 할 수 있다. (H ≤ T)

산타 할아버지는 한 번 주문할 때마다, 주문한 상자에 있는 인형들을 모두 꺼내서 각각을 K명에게 정확히 같은 수만큼 나누어 주고, 남는 인형이 없도록 한다.

1. 한 번 주문할 수 있다면, 가능한 주문 방법은 몇 가지인가?

2. 여러 번 주문할 수 있다면, 주문이 겹치지 않게 최대 몇 번 주문할 수 있는가? (주문이 겹친다는 것은 어떤 두 주문에 같은 번호의 인형 상자가 포함되는 것을 말한다.)

입력

첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. ( T ≤ 60 )

각 테스트 케이스의 첫 번째 줄에는 인형 상자의 개수 N과 어린이의 수 K가 주어진다.(1 ≤ N, K ≤ 100000)

두 번째 줄에는 1번 인형 상자부터 N번 인형 상자까지 각 인형 상자에 들어 있는 인형의 개수 Di가 주어진다. ( 1 ≤ i ≤ N, 1 ≤ Di ≤ 100000 )

 

출력

1번에 대한 답과 2번에 대한 답을 한 줄에 하나의 빈칸으로 나누어 출력한다. 1번 답은 매우 클 수 있으므로 20091101로 나눈 나머지를 출력한다.

---

구간합을 활용한 문제이다. 구간합을 구하는 배열 psum에 값을 그냥 더해주는 게 아닌 K의 나머지를 저장하는게 중요한 포인트였다.

 

우선 첫번째 질문에 대한 답을 식으로 풀어보면 (psum[T] - psum[H-1]) mod K = 0이 되는데 psum자체를 K로 나누면 psum[T] == psum[H-1]인 지점만 찾으면 된다. K보다 작은 값 중 같은 값 두개를 고르면 되는 문제이므로 같은 값이 나온 수 중 2개를 구하면 된다. 순열 조합 공식으로 

N * (N-1) / 2 를 결과값에 더해준다.

 

두 번째 질문은 문제가 이해가 되지 않아 힘들었지만 동적 프로그래밍을 이용한 문제이다.

maxBuy(i) : 0번 상자부터 i번 상자까지 겹치지 않고 구매하는 부분 구간의 최대수라고 놓고 이에 대응하는 배열을 res[i]라고 하자.

prev[s] = psum[]이 s였던 마지막 위치라고 하면

res[i] = max( res[i-1], res[prev[psum[i]]]+ 1) 이다. 앞의 항은 i번째 상자를 아예 고르지 않은 경우이고, 뒤의 항은 i번째 상자를 골랐을 때 i번 상자까지의 합과 똑같은 저번 상자까지 모두 구매하는 경우이다. 예를들어 psum[10] = 4이고 psum[5] = 4라고 하면 5번 상자부터 10번상자까지 모두 구매했다는 뜻이다. 이 점화식을 풀면 답을 구할 수 있다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/CHRISTMAS.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int C, N, K;
const int mod = 20091101;

int waysToBuy(const vector<int> &psum)
{
	vector<long long> count(K, 0);
	for (int i = 0; i < psum.size(); i++)
		count[psum[i]]++;

	int res = 0;
	for (int i = 0; i < K; i++) {
		if (count[i] >= 2)
			res = (res + (count[i] * (count[i] - 1) / 2)) % mod;
	}
	return res;
}

int maxBuy(const vector<int> &psum)
{
	vector<int> res(psum.size(), 0);
	vector<int> prev(K, -1);
	for (int i = 0; i < psum.size(); i++) {
		if (i > 0) res[i] = res[i - 1];
		else res[i] = 0;

		int loc = prev[psum[i]];
		if (loc != -1) res[i] = max(res[i], res[loc] + 1);
		prev[psum[i]] = i;
	}
	return res.back();
}

int main()
{
	cin >> C;
	while (C--) {
		cin >> N >> K;
		vector<int> p(N, 0);
		vector<int> psum(N + 1, 0);
		for (int i = 0; i < N; i++) 
			cin >> p[i];

		psum[0] = 0;
		for (int i = 1; i <= N; i++) {
			psum[i] = (psum[i - 1] + p[i - 1]) % K;
		}
		cout << waysToBuy(psum) << " " << maxBuy(psum) << endl;
	}
}