<문제 링크>
https://algospot.com/judge/problem/read/CHRISTMAS
이 문제는 인형 구매를 위한 조건을 수식으로 나타내고 수식을 적절한 형태로 변화시키면 반정도 풀었다고 생각된다. 하지만 여기서 오버플로우를 신경 못쓴다면 AC를 받지 못한다. 절대로...ㅋ
문제는 아래와 같다.
크리스마스를 맞이하여 산타 할아버지는 전세계의 착한 어린이 K명에게 인형을 사주려고 한다. 산타 할아버지는 인형을 구입하기 위해서 유명한 인형가게인 "놀이터"에 찾아갔다. 놀이터에는 N개의 인형 상자가 한 줄로 진열되어 있고, 각 인형 상자에는 한 개 이상의 인형이 들어 있다. 그리고 놀이터에서는 주문의 편의성을 위해 각 상자에 번호를 붙여 놓았고, 주문은 "H번 상자부터 T번 상자까지 다 주세요."라고만 할 수 있다. (H ≤ T)
산타 할아버지는 한 번 주문할 때마다, 주문한 상자에 있는 인형들을 모두 꺼내서 각각을 K명에게 정확히 같은 수만큼 나누어 주고, 남는 인형이 없도록 한다.
- 한 번 주문할 수 있다면, 가능한 주문 방법은 몇 가지인가?
- 여러 번 주문할 수 있다면, 주문이 겹치지 않게 최대 몇 번 주문할 수 있는가? (주문이 겹친다는 것은 어떤 두 주문에 같은 번호의 인형 상자가 포함되는 것을 말한다.)
우슨 부분합에 대한 개념이 필요하다. 각 인형을 구매할시 연속된 상자들만 구매가 가능 하다. 이때에 구매 가능 여부를 따지기 위해서는 연속된 상자들의 인형의 총합을 k로 나눈 나머지가 필요한데 이때 연속된 상자들의 합을 부분합 개념을 이용해서 O(1)에 구할 수 있다. 이렇게 구해진 부분합을 이용해 상자 구매 가능 조건을 식으로 나타내면 아래와 같다.
psum[i] = 0 부터 i번째 상자까지의 인형의 총 갯수.
(psum[i] - psum[j - 1]) % k == 0 이면 i부터 j까지의 상자들은 구매가 가능하다.
모듈러 연산의 분배가 가능하다는 것을 고려하면 위 조건식은 아래와 같이 변경 가능하다.
psum[i] % k == pusm[j - 1] % k
결과적으로 상자의 구매가 가능하기 위해서는 우리가 구해놓은 부분합을 k로 나눈 나머지가 같은 상자들만 구매가 가능하다. 이와 같은 성질을 이용하여 우리는 위의 두 문제를 해결할 수 있다.
문제 해결을 위해 psum을 새롭게 정의하면 아래와 같다.
psum[i] = 0부터 i - 1까지의 합을 k로 나눈 나머지
이때 psum[0]은 0을 삽입한다. 이유인 즉슨 이러하다 psum[i]을 k로 나눈 나머지가 0인 구간은 0부터 i까지의 상자들을 구매가 가능하다. 하지만 위에서 우리가 유도한 수식을 이용해서 이러한 경우 까지 답을 구하기 위하여 위와같은 psum배열의 변형이 필요했던 것이다. 이렇게하면 항상 psum[0] = 0 이기 때문에 값이 0인 psum들도 다른 psum들과 마찬가지로 본인과 같은 값을 갖는 psum이 있을때에만 구매가 가능하게 된다.
1.한번 주문할 수 있다면, 가능한 주문 방법은 몇 가지인가?
첫째. psum을 순회하면서 psum이 갖는 값들의 갯수를 센다. psum이 갖는 값은 k로 나눈 나머지이므로 0 ~ k - 1까지가 있을 수있다.
둘째. 첫째에서 0 ~ k - 1까지의 값들이 각 몇개씩 있는지 구했으므로 이제 이들의 갯수가 2개 이상인 값들은 이들중 둘을 고르는 조합값을 다 더하면 우리가 원하는 해를 구할 수 있게된다. 코드는 아래와 같다.
const int MOD = 20091101;
vector<int> psum;
int doll[100000];
psum.resize(n + 1);
psum[0] = 0;
for(int i = 1; i <= n; ++i)
//오버플로우 조심. 예를 들어 psum을 다구하고나서 k로 나누면 오버플로우 발생
psum[i] = (psum[i - 1] + doll[i - 1]) % MOD;
//구매 가능한 횟수를 반환한다.
int waysToBuy(){
//count[i] = 나머지가 i인 psum의 갯수를 저장한다.
vector<long long> count(k, 0);
for(int i = 0; i <= n; ++i)
++count[psum[i]];
int ret = 0;
for(int i = 0; i < k; ++i)
if(count[i] >= 2)
//count[i]를 곱하는 부분에서 상한이 거의 10^10 에 가깝기 때문에
//int로 선언했을시 오버플로우가 발생한다.
ret = (ret + (count[i] * (count[i] - 1)) / 2) %MOD;
return ret;
}
2.여러번 주문할 수 있다면 겹치지 않게 최대 주문 가능한 횟수는 몇번 인가?
1번 문제를 풀면서 이문제를 풀기위해 필요한 키포인트를 이미 다 알고있는 셈이다. 우리는 이 정보를 바탕으로 동적계획법을 구현하면 문제를 해결할 수 있다.
dp[i] = i - 1번 상자까지 구매 가능한 최대 횟수
//i - 1번째 인형을 구매하지 않거나? 구매할 경우 둘중의 최댓값을 저장
dp[i] = max(dp[i -1], dp[최근에 psum값이 같았던 인덱스] + 1);
위와같은 점화식을 이용하여 문제를 해결하기 위해서는 최근에 psum값이 같았던 인덱스를 알아야된다. 우리는 이 정보만 배열에 따로 저장해두고 최신화 하면서 동적계획법을 구현하면 두번째 문제 또한 해결할 수 있다. 코드는 아래와 같다.
//psum선언 밑 초기화
...
//최대 구매 횟수 반환
int maxBuys(){
vector<int> dp(n + 1, 0);
//psum값에따른 인덱스를 저장하는 벡터
vector<int> prev(k, -1);
prev[psum[0]] = 0;
for(int i = 1; i <= n; ++i){
if(prev[psum[i]] == -1)
dp[i] = dp[i - 1];
else
dp[i] = max(dp[i - 1], dp[prev[psum[i]] + 1);
}
return dp[n];
}