[BOJ][백준] 20958번: 아린과 슬롯머신

www.acmicpc.net/problem/20958

20958번: 아린과 슬롯머신

 

문제

아린은 강원랜드로 휴가를 떠났다(아린은 감염병 예방을 위한 정부의 방역지침을 준수한다). 강원랜드에서 가장 인기 있는 게임은 슬롯머신이다. 슬롯머신을 구경하던 아린은 놀라 자빠질 수밖에 없었다. 잭팟이 터질 경우 거액의 당첨금을 받을 수 있다는 정보를 입수하였기 때문이다. 아린은 잭팟을 터트려 집도 사고 차도 사고 맛있는 것도 많이 먹기로 결심하였다.

아린은 칸의 개수가 N개인 슬롯머신을 가지고 있다. 슬롯머신의 레버를 당길 때마다 각 칸에는 임의의 양의 정수가 표시된다. 이때 모든 칸에 7이 표시되면 잭팟이 터졌다고 하며, 잭팟이 터지면 거액의 당첨금이 지급된다.

하지만 슬롯머신을 작동시키기 위해서는 돈이 필요하다. 검소하기로 유명한 아린은 슬롯머신 따위에 돈을 낭비하지 않는다. 슬롯머신을 작동시키는 대신, 아린은 슬롯머신의 각 칸에 대하여 다음과 같은 연산을 무한히 수행할 수 있다. 구간 [i, i + M)과 7이 아닌 소수 p를 선택한다. 그리고 구간에 속하는 수 중 p로 나누어 떨어지는 모든 수를 p로 나눈다. 즉, Si, Si+1,..., Si+M-1 중 p로 나누어떨어지는 모든 수를 p로 나눈다. (1 ≤ i ≤ N - M + 1, p ≠ 7)

슬롯머신의 상태가 주어졌을 때, 잭팟을 터트리기 위하여, 즉 모든 수를 7로 바꾸는 데 필요한 최소 연산 횟수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 슬롯머신의 칸의 개수 N과 구간의 길이 M이 주어진다.

두 번째 줄에 슬롯머신의 각 칸에 표시된 N개의 정수 S1, S2,..., SN이 주어진다.

모든 입력은 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 잭팟을 터트리기 위하여 필요한 최소 연산 횟수를 출력한다. 모든 수를 7로 바꿀 수 없다면 -1을 출력한다.

제한

• 1 ≤ N ≤ 50,000
• 1 ≤ M ≤ N
• 1 ≤ Si ≤ 10,000,000

---

문제 접근방법을 찾기가 조금 까다롭습니다. 구간을 업데이트하는데 그게 소수로 나눈 몫이어야 하고 모든 수를 7로 만들어야 하는.. 우선 소수를 구해야 할 것 같으니 10^7 이하의 소수를 모두 구해줍시다.

bool isPrime[MAX_N];
vector<int>prime;

void getPrime() {
	for (int i = 0; i < MAX_N; i++)isPrime[i] = true;
	isPrime[0] = false, isPrime[1] = false;
	for (int i = 2; i < MAX_N; i++) {
		if (isPrime[i]) {
			prime.push_back(i);
			for (int j = i + i; j < MAX_N; j += i) {
				isPrime[j] = false;
			}
		}
	}
}

그 후 prime의 사이즈를 구해보니 664579라는 수가 나옵니다. N제한이 5만이니 각 소수별로 수열을 쭉 살펴보면서 답을 구하면 60만*5만이니 시간 초과입니다. 우선 시간 초과라도 코드를 한번 작성해 봅시다. 각 소수 별로 수열을 한 번만 살펴보면 어떻게 답을 구할 수 있을까요?

그 해답은 그리디로 접근하면 됩니다. 모든 수열이 나누어 떨어져야 하니, 수열을 앞으로부터 보면서 나누어 떨어진다면 모두 나누는 것이 최적입니다. 그리고 그 위치에서 나눈다면 구간 [i, i + M)까지 모두 나눠지겠죠. 예를 들어봅시다.

8 16 4 32 2

(문제는 모든 수열을 7로 만들어야 하지만 우리는 선처리 후 1로 만든다고 생각합시다.) 소수 2일 때 수열을 살펴본다고 생각한다면,  다음과 같이 로직을 생각할 수 있습니다. 대출을 받는다고 생각하고, M일 후 다시 상환한다고 상황을 가정해본다면,

	8	16	4	32	2
대출	+3(2^3)	+1(2^1)		+4(2^4)
상환			-3(2^3)	-1(2^1)

다음과 같이 총 8번의 대출을 받는다고 볼 수 있습니다. 수열의 처음인 8에서 3만큼의 대출을 받고(2^3=8), 그다음 16에선 4만큼의 대출이 필요한데(2^4=16) 우린 이미 3만큼의 대출이 있으므로 대출을 하나 더 받습니다. 그 후 4에서는 우리에게 4만큼의 대출이 있으니(2^4=16) 대출을 안 받아도 됩니다. 하지만 M만큼의 길이가 끝났으므로 처음 8에서 빌린 3만큼을 갚습니다. 따라서 1의 대출이 남게 됩니다. 이런 식으로 진행을 하면 됩니다. 그렇다면 다음과 같이 코드를 작성할 수 있습니다.

for (auto p : prime) {
		int arr[100000 + 2] = { 0, };
		int pow = 0;
		for (int i = 0; i < N; i++) {
			int&now = v[i], cnt = 0;
			while (now%p == 0) {
				now /= p;
				cnt++;
			}
			if (pow < cnt) {
				ans += cnt - pow;
				arr[i + M - 1] = cnt - pow;
				pow = cnt;
			}
			pow -= arr[i];
		}
	}

pow를 대출이라고 생각하고, cnt는 받아야 하는 대출을 계산하는 변수입니다. 하지만 아직 풀어야 할 숙제가 남아있죠.

O(소수의 개수(66만) * 수열의 길이(5만))

어떻게 이 시간 복잡도를 줄일 수 있을까요? 수열의 길이를 줄이긴 힘들어 보이고, 소수의 개수를 줄인다면?

3163이라는 소수를 생각해 봅시다. 3163*3163=10,004,569. 수열의 수의 최댓값인 10^7을 넘는 소수입니다. 뭔가 새로운 발견을 할 수 있지 않을까요? 3163을 넘는 소수는 대출을 최대 1까지만 필요로 합니다. 즉 3163 이상의 소수를 알파벳으로 생각을 한다면, 다음과 같은 수열로 변환해 볼 수 있습니다.

A B A C C B A

A*B 같은 형태는 절대 나올 수 없습니다. 3163^2는 입력의 최댓값을 넘는 값이기 때문이죠. 이 수열을 A를 대출받고, B를 대출받는 형태로 나타낸다면,

	A	B	A	C	C	B	A
대출	+A	+B		+C		+B	+A
상환			-A	-B		-C

다음과 같이 나타낼 수 있습니다. 해석하는 방법은 위와 동일합니다. 대출과 상환을 구현하는 방식은 set의 insert, erase함수를 이용하면 될 겁니다. 이 방식을 코드로 옮긴다면 다음과 같습니다.

	set<int>st;
	st.insert(1);
	int arr[100000 + 2] = { 0, };
	for (int i = 0; i < N; i++) {
		int now = v[i];

		if (st.find(now) == st.end()) {
			st.insert(now);
			arr[i + M - 1] = now;
			ans++;
		}
		if (arr[i] != 0) {
			st.erase(arr[i]);
		}
	}

 

정리하자면, 이 문제를 2개로 분할할 수 있습니다. key number인 3163을 기준으로, key number보다 적은 소수는 각 소수 별로 수열을 모두 살펴보며 제거를 해줍니다. 그렇다면 수열에 남은 수는 모두 1 혹은 key number이상의 소수가 남게 됩니다. 그 소수는 set을 사용하여 위와 같은 방식으로 해결하면 됩니다. 모든 걸 총 정리한 코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <set>
using namespace std;
const int MAX_N = 1e7 + 2, keyNum = 3163;

bool func(vector<int>&v) {
	for (auto& i : v) {
		if (i % 7 != 0)return false;
		i /= 7;
		if (i % 7 == 0)return false;
	}
	return true;
}
bool isPrime[MAX_N];
vector<int>prime;

void getPrime() {
	for (int i = 0; i < MAX_N; i++)isPrime[i] = true;
	isPrime[0] = false, isPrime[1] = false;
	for (int i = 2; i < MAX_N; i++) {
		if (isPrime[i]) {
			prime.push_back(i);
			for (int j = i + i; j < MAX_N; j += i) {
				isPrime[j] = false;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	getPrime();
    
	int N, M, ans = 0;
	cin >> N >> M;
	vector<int>v(N);
	for (auto&i : v)cin >> i;
	if (!func(v)) {
		cout << -1;
		return 0;
	}
	for (auto p : prime) {
		if (p >= keyNum)break;
		int arr[100000 + 2] = { 0, };
		int pow = 0;
		for (int i = 0; i < N; i++) {
			int&now = v[i], cnt = 0;
			while (now%p == 0) {
				now /= p;
				cnt++;
			}
			if (pow < cnt) {
				ans += cnt - pow;
				arr[i + M - 1] = cnt - pow;
				pow = cnt;
			}
			pow -= arr[i];
		}
	}
	set<int>st;
	st.insert(1);
	int arr[100000 + 2] = { 0, };
	for (int i = 0; i < N; i++) {
		int now = v[i];

		if (st.find(now) == st.end()) {
			st.insert(now);
			arr[i + M - 1] = now;
			ans++;
		}
		if (arr[i] != 0) {
			st.erase(arr[i]);
		}
	}
	cout << ans;
}

시간 복잡도를 줄이기 위해 문제를 두 부분으로 나눠 해결하는 방식이 인상적이었던 문제였습니다. key number는 꼭 3163일 필요는 없습니다. 실제로는 모든 수열은 7*N <10^7 형태이기 때문에 더 작을 수 있기에 푸는 방식에 따라 달라질 겁니다. 접근방법을 찾는 것도 까다로웠지만 코드 작성 시 오류가 있어 낮은 정답률이 나왔습니다.