study/coding test

[Algospot] 크리스마스 인형 - CHRISTMAS

Acver 2022. 1. 25. 13:27

1. 문제 정리

  - K명에게 동일하게 선물을 나눠주려 한다.

  - N개의 인형 상자가 있으며, 각 상자에는 한개 이상의 인형이 들어있다.

  - 상자는 순서대로 번호가 매겨져 있으며, 주문은 반드시 "H번 상자부터 T번 상자까지 다 주세요"라고만 해야한다.

  - 주문한 상자의 인형들을 모두 꺼내 K명에게 같은 수만큼 나누어준다.

  - 한번 주문할 때, 가능한 주문 방법의 수는 몇인가? 20091101로 나눈 값을 출력한다.

  - 여러 번 주문할 때, 주문이 겹치지 않게 주문하는 횟수의 최대값을 출력한다.

 

2. 접근
  - 부분합으로 접근한다.

  - 한번 주문할 때의 경우의 수에 대해서는 부분합이 psum[]이라 하였을 때, (psum[T] - psum[H-1]) % K == 0이 되어야 하므로, 이는 즉, psum[T] % K == psum[H-1] % K를 의미하므로 전제 부분 합을 보았을 때, 같은 값이 존재하는 경우에 대하여 고려한다.

  - 여러번 주문할 때의 경우의 수에 대해서는 DP를 사용하여야 한다. DP[i]의 값을 0번째 상자부터 i번째 상자까지 샀을 때, 가능한 최대 주문의 수라고 하면 해당 DP 값에는 i 번째 상자를 샀을 때, 그리고 사지 않았을 때의 값 중 최대값이 들어갈 것이다.

 즉, DP[i] = max(DP[i-1], DP[최근에 psum이 같았던 인덱스] + 1)로 순서대로 i를 사지 않았을 때, 샀을 때 중 최대값을 DP[i]에 넣는 과정이라 볼 수 있다.

 "최근에 psum이 같았던 인덱스"를 알기 위해 이를 저장할 다른 벡터를 선언한다.

 

3. 풀이

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

int waysToBuy(vector<int> &psum, int K){
	const int MOD = 20091101;
	int result = 0;

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

	for (int i = 0; i < K; i++)
		if (count[i] >= 2)

			result = (result + ((count[i] * (count[i] - 1)) / 2)) % MOD;

	return result;
}

int maxBuys(vector<int> &psum,int K){
	vector<int> result(psum.size(),0);
	vector<int> previous(K,-1);
	
	for (int i = 0; i < psum.size(); i++)
	{
		if (i > 0)
			result[i] = result[i - 1];
		else
			result[i] = 0;
		
		int loc = previous[psum[i]];

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

int main() {
	int T;
	cin >> T;

	for(int i = 0;i<T;i++){
		int N,K;
		cin >> N >> K;
		vector<int> D(N);

		for(int j = 0;j<N;j++){
			cin >> D[j];	
		}
		
		vector<int> psum(N+1);
		psum[0] = 0;
		
		for(int z = 1;z<=N;z++){
			psum[z] = (psum[z-1] + D[z-1]) % K;	
		}

		cout << waysToBuy(psum,K) << " "<< maxBuys(psum,K) << endl;
		
	}	
	return 0;
}

  - int waysToBuy(vector<int> &psum, int K) : 한번만 주문할 수 있을 때 최대 경우의 수를 구하는 함수이다.

    - const int MOD : 오버플로우를 방지하기 위해 나누어줄 수를 상수로 선언한다.

    - vector<long long> count(K, 0) : psum에서 같은 값을 갖는 수의 수를 체크하기 위한 벡터로, 인덱스에는 psum이 들어간다.

    - for(int i = 0; i < psum.size(); i++) : psum에 존재하는 같은 값들의 수를 저장하는 동작이다.

    - for(int i = 0; i < K; i++) : count값이 2 이상인 수들을 갖고와 두개씩 짝 지어 경우의 수를 계산한다. 즉, nC2로 계산을 한다.(여기서 n은 count[i]가 된다.) count 값이 2 이상인 수에 한하는 것은 접근에서도 나왔듯이, psum[T] % K == psum[H-1] % K가 성립해야 하며, 이는 즉 psum[T] == psum[H-1] (psum에 저장할 때 K로 나눈 나머지를 저장하므로)을 의미하고, 이를 성립하는 조건이 count[pusm[T]] >= 2가 된다.

  - int maxBuys(vector<int> &pusm, int K) : 여러번 주문할 수 있을 때 최대 경우의 수를 구하는 함수이다.

    - vector<int> result(psum.size(), 0) : dp를 수행한 값들을 저장할 벡터이다.

    - vector<int> previous(K, -1) : psum에 저장된 각 값에 대하여, 해당 값을 마지막으로 본 인덱스가 몇번인지를 기록해둔다.

    - for(int i = 0; i < psum.size(); i++)

      - if(i>0) : 일반적인 경우에 대해, result[i]값에 이전 값인 result[i-1]을 넣어둔다.

      - else : 즉, i == 0인 경우에 대한 것인데, 이때는 0을 넣어둔다. 이는 array boundary를 위함이며, 의미 상으로도 첫번째 값 이전에 상자는 존재하지 않으므로 0을 넣어 주게 된다.

      - int loc = previous[psum[i]] : 현재 보고 있는 부분합과 같은 부분합을 마지막으로 본 인덱스의 값을 loc에 저장한다.(만약 이번에 처음 보는 부분합이었다면, -1이 들어갈 것이다.)

      - if(loc != 1) : 처음 방문한 것이 아니라면, result[i]값에, result[i]와 result[loc]+1 중 더 큰값을 넣고, previous[psum[i]]값을 현재 값(i)으로 갱신해준다.

  - int main()

    - vector<int> psum(N+1); psum[0] = [0]; : 이후 계산의 편의를 위해 첫번째 값 이전에 아무것도 더하지 않았다는 의미인 0을 넣어놔준다.

    - for(int z = 1; z <= N; z++) : 부분합을 psum에 넣어주되, 이후 계산의 편의를 위하 K로 나눈 나머지값만 넣어준다.

 


4. 후기

  나에겐 꽤나 어려운 문제였다. 하나의 문제에 두개의 문제가 겹쳐져 있는 경우였으며, 부분합에 DP를 더하는 것까지 꽤나 버거웠다. 아직 혼자서 풀어보라고 하면 꽤나 많은 시간이 걸릴 것 같은 문제이다. 특히 문제의 답을 내보내는 것까지는 구현을 했으나, 이번 문제 같은 경우에는 계속 시간초과가 발생하였다. 식을 이용하여 같은 값의 수를 구하고, 그걸 조합을 이용하여 경우의 수를 구할 생각을 하지 못하여 이중 for문을 사용하였고, DP에서 또한 previous 벡터를 생각해내지 못해 이중 배열을 사용하였다.

 아직 부족함을 많이 느낄 수 있게 해준 문제였고, 모자란 부분을 더욱 많이, 탄탄히 채워나가야겠다고 생각을 하도록 해준 문제였다.

저작자표시 (새창열림)