백준 20952: 게임 개발자 승희

https://www.acmicpc.net/problem/20952

 

단순하게는 풀리진 않는다.

이 문제는 수열 A와 수열 B의 길이가 각각 100,000이 넘는 것이 문제다.

따라서 단순하게 계산을 하면 최대 100,000 * 100,000 = 약 10억으로 시간초과가 될 것은 불보듯 뻔하다.

 

그럼 수열 B를 전부 더 한 뒤에, 수열 A에 더한 뒤, 7의 배수가 아닌 수를 배제하면 어떨까?

그러면, 연산 중에 7의 배수가 아닌 수를 배제할 수 없다. 따라서 이것도 아니다. 도대체 정답이 뭘까?

 

연대 책임

나는 여기서 예제 입력 2에 주목하였다.

7 7
7 14 21 28 35 42 49
7 7 7 7 7 7 7

이 예제의 수열 A는 어떠한 7의 배수 값을 더해도, 모든 원소가 제거된다. 반면, 7의 배수가 아닌 어떠한 값을 더해도 수열 A의 어떠한 값도 사라지지 않는다.

 

즉, 7로 나누었을 때, 나머지가 같은 값들은 같은 운명이다. 이를 통해, 나머지로 수열 A의 값들을 그룹핑할 수 있다!

예로 수열 A가 다음과 같이 주어졌다 가정하자.

8
1, 8, 13, 17, 23, 25, 33, 34

그러면

- 7로 나누었을 때
나머지가 0: 35
나머지가 1: 1, 8
나머지가 2: 23
나머지가 3: 17, 38
나머지가 4: 25
나머지가 5: 33
나머지가 6: 13

이렇게 그룹핑을 할 수 있다.

이 다음, 수열 B를 앞에서부터 순회하며, 값을 더한다. 그리고, 그 값을 더했을 때, 7의 배수가 되는 값들을 배제한다.

예를 들어 수열 B가

7
1, 3, 5, 8, 3, 1, 5

라고하자.

여기서, 우선 1을 더했을 때, 7의 배수가 되는 값을 제거한다. 즉, 나머지가 6인 값들(13)을 제거한다.

그 다음 1에 3을 더해 4를 만든 뒤, 4를 더했을 때, 7의 배수가 되는 나머지가 3인 값들(17, 38)을 제거한다.

5을 더해 9를 만든 뒤, 9를 더했을 때, 7의 배수가 되는 나머지가 5인 값들(33)을 제거한다.

8을 더해 17을 만든 뒤, 17을 더했을 때, 7의 배수가 되는 나머지가 4인 값들(25)을 제거한다.

3을 더해 20을 만든 뒤, 20을 더했을 때, 7의 배수가 되는 나머지가 1인 값들(1, 8)을 제거한다.

1을 더해 21을 만든 뒤, 21을 더했을 때, 7의 배수가 되는 나머지가 0인 값들(35)을 제거한다.

5를 더해 26을 만든 뒤, 26을 더했을 때, 7의 배수가 되는 나머지가 2인 값들(23)을 제거할 차례인데, 이것을 제거하면, 수열 A가 모두 제거되기 때문에 이 명령은 넘어간다.

 

이런 방식으로 답을 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
ll A, B, s = 0;
int N, M;
vector<pair<int, ll>> S[7];
vector<pair<int, ll>> ans;
bool v[7];
int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> A;
		S[A % 7].push_back({ i, A });
	}
	for (int i = 0; i < M; i++)
	{
		cin >> B;
		int idx = (7 - ((s + B) % 7)) % 7;
		if (N == S[idx].size()) continue;
		s += B;
		if (v[idx]) continue;
		v[idx] = true;
		N -= S[idx].size();
	}
	for(int i = 0 ;i < 7; i++)
		if (!v[i])
			for (int j = 0; j < S[i].size(); j++)
				ans.push_back(S[i][j]);
	sort(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++)
		cout << (ans[i].second + s) % 1000000007 << " ";
	cout << '\n';
}

별 다른 알고리즘 없이 재미있는 문제였다.