🚀 [CHRISTMAS] 문제 😭😭😭😭😭
크리스마스를 맞이하여 산타 할아버지는 전세계의 착한 어린이 K명에게 인형을 사주려고 한다. 산타 할아버지는 인형을 구입하기 위해서 유명한 인형가게인 “놀이터”에 찾아갔다. 놀이터에는 N개의 인형 상자가 한 줄로 진열되어 있고, 각 인형 상자에는 한 개 이상의 인형이 들어 있다. 그리고 놀이터에서는 주문의 편의성을 위해 각 상자에 번호를 붙여 놓았고, 주문은 “H번 상자부터 T번 상자까지 다 주세요.”라고만 할 수 있다. (H ≤ T)
산타 할아버지는 한 번 주문할 때마다, 주문한 상자에 있는 인형들을 모두 꺼내서 각각을 K명에게 정확히 같은 수만큼 나누어 주고, 남는 인형이 없도록 한다.
- 한 번 주문할 수 있다면, 가능한 주문 방법은 몇 가지인가?
- 여러 번 주문할 수 있다면, 주문이 겹치지 않게 최대 몇 번 주문할 수 있는가? (주문이 겹친다는 것은 어떤 두 주문에 같은 번호의 인형 상자가 포함되는 것을 말한다.)
🔑 [풀이]
H에서 T까지 상자를 구매할 때 남기지않고 아이들에게 나눠질 수 있는 여부는 K로 나누어 떨어지느의 여부입니다.
박스에 담긴 부분합들을 boxSum 에 저장합니다. ( boxSum = \(\sigma (i번째 상자)% K\) 로 나타낸다.)
첫째 질문은 코드참고바람.
두번째 질문은
\(ret[i] =
\begin{cases}
ret[i-1]\\
ret[prev[boxSum[i]]] +1 \t (prev[psum[i]] \neq -1)
\end{cases}\)
⌨️ 입력
첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. ( T ≤ 60 )
각 테스트 케이스의 첫 번째 줄에는 인형 상자의 개수 N과 어린이의 수 K가 주어진다.(1 ≤ N, K ≤ 100000)
두 번째 줄에는 1번 인형 상자부터 N번 인형 상자까지 각 인형 상자에 들어 있는 인형의 개수 Di가 주어진다. ( 1 ≤ i ≤ N, 1 ≤ Di ≤ 100000 )
🖥 출력
1번에 대한 답과 2번에 대한 답을 한 줄에 하나의 빈칸으로 나누어 출력한다. 1번 답은 매우 클 수 있으므로 20091101로 나눈 나머지를 출력한다.
🖱 입력 예제
1
6 4
1 2 3 4 5 6
💻 출력 예제
3 1
💎 전체 코드는 다음과 같습니다.
//
// CHRISTMAS.cpp
// AALGGO
//
// Created by inhyeok on 2021/11/27.
//
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("CHRISTMAS.txt");
int N; // 인형 상자의 개수
int K; // 어린이의 수
int firstQ(const vector<int> &boxSum){
const int MOD = 20091101;
int result = 0;
//psum[]의 각 값을 몇 번이나 본 적 있는지 기록
vector<long long> count(K, 0);
for (int i = 0; i < boxSum.size(); i++)
count[boxSum[i]]++;
//두 번 이상 본 적 있다면 이 값 중 두 개를 선택하는 방법의 수를 더한다
//count[i]개 중 2개를 고를 경우의 수
//nC2를 더한다 (n=count[i])
for (int i = 0; i < K; i++)
if (count[i] >= 2)
result = (result + ((count[i] * (count[i] - 1)) / 2)) % MOD;
return result;
}
int secondQ(const vector<int> &boxSum){
vector<int> ret(boxSum.size(),0);
//prev[S] = boxSum[] 이 마지막 S였던 위치
vector<int> prev(K, -1);
for(int i=0; i<boxSum.size(); i++){
// i번째 상자를 고려하지 않는경우
if(i>0)
ret[i] = ret[i-1];
else ret[i] = 0;
int loc = prev[boxSum[i]];
if(loc !=-1) ret[i] = max(ret[i], ret[loc] +1);
prev[boxSum[i]] = i;
}
return ret.back();
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test<test_case; test++){
fin >> N >> K;
vector<int> boxSum(N+1,0);
vector<int> box(N,0);
for(int i=0; i<N; i++){
fin >>box[i];
}
boxSum[0] = 0;
for(int i=1; i<N+1; i++){
boxSum[i] = (boxSum[i-1] + box[i-1]) % K;
}
cout << firstQ(boxSum) << " " << secondQ(boxSum) << endl;
boxSum.clear();
}
}
Comments