[백준] 19595 소수 게임

⚡백준 19595 소수 게임

• https://www.acmicpc.net/problem/19595

• 구간 합 알고리즘을 적용해도 시간 초과 해결이 안된다
  시간을 줄일 수 있는 또다른 방법을 생각해봐야겠다

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
using namespace std;

const int MAXN = 100000;
int cache[MAXN];
int sum[MAXN];
int isPrime[MAXN];

//에라토스테네스의 체
void setIsPrime() {
	memset(isPrime, 1, sizeof(isPrime));
	isPrime[0] = isPrime[1] = 0;

	for (int i = 2; i <= sqrt(MAXN); i++) {
		if (isPrime[i] == 0) continue;

		for (int j = i * i; j <= MAXN; j += i)
			isPrime[j] = 0;
	}
	return;
}

//현재 종이에 적힌 숫자가 N일 때 
//현재 차례가 이길 수 있으면 1, 지면 0 반환
int canWin(int N) {
	if (N == 0 || N == 1) return 0;
	if (isPrime[N]) return 1;

	int& ret = cache[N];
	if (ret != -1) return ret;

	ret = 0;
	for (int i = 2; i <= N; ++i) {
		if (isPrime[i])
			//다음 차례에서 지는 경우에 현재 차례에서 이길 수 있다
			if (!canWin(N - i)) {
				ret = 1;
				break;
			}
	}
	return ret;
}

void getSum() {
	memset(sum, 0, sizeof(sum));

	for (int N = 2; N <= MAXN; ++N) 
		sum[N] = sum[N - 1] + !canWin(N);

	return;
}

void getX(int A, int k) {

	int bestX = 0;
	int bestwin = 0;

	for (int X = A + 1 - k; X >= 2; --X) {
		int win = sum[X + k - 1] - sum[X - 1];

		if (bestwin <= win) {
			bestwin = win;
			bestX = X;
		}
	}

	cout << bestwin << " " << bestX << "\n";
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(cache, -1, sizeof(cache));

	setIsPrime();
	getSum();

	int T;
	cin >> T;
	while (T--) {
		int A, k;
		cin >> A >> k;
		getX(A, k);
	}

	return 0;
}

풀이 (recursive)

• 2 ~ MAXN 범위 내의 소수들을 prime 벡터 따로 저장
  -> canWin()함수 속 for문의 반복 횟수 MAXN -> prime벡터의 크기로 감소
  -> 시간 초과 해결

vector<int> prime;

void getPrime() {
	for (int i = 2; i <= MAXN; ++i)
		if (isPrime[i]) 
			prime.push_back(i);
	return;
}

//현재 종이에 적힌 숫자가 N일 때 
//현재 차례가 이길 수 있으면 1, 지면 0 반환
int canWin(int N) {
	if (N == 0 || N == 1) return 0;
	if (isPrime[N]) return 1;

	int& ret = cache[N];
	if (ret != -1) return ret;

	ret = 0;
	for (int i = 0; i < prime.size(); ++i) {
		if (prime[i] > N) break;
		//다음 차례에서 지는 경우에 현재 차례에서 이길 수 있다
		if (!canWin(N - prime[i])) {
			ret = 1;
			break;
		}
	}
	return ret;
}

풀이 (iterative)

• 재귀 함수 canWin() 대신, 반복적으로 배열 canWin[]의 값을 계산하는 풀이

• 재귀적 풀이 -> 메모리: 3328KB, 시간: 444ms
  반복적 풀이 -> 메모리: 3328KB, 시간: 112ms

	int psize = prime.size();
	for (int i = 0; i <= MAXN; i++) {
		if (canWin[i])
			continue;
		for (int j = 0; j < psize; j++)
		{
			if (i + prime[j] > MAXN)
				break;
			canWin[i + prime[j]] = 1;
		}
	}

📌참고자료

• 구간 합(prefix sum)
  https://kosaf04pyh.tistory.com/320

• 구간 합 알고리즘: 1차원배열에서 i ~ k번째 사이의 값들의 합을 구하는데 사용
  -> 단순히 for문을 사용하여 i~k사이의 값을 더해가는 경우: O(N)
  -> 구간 합 알고리즘의 경우: O(1)

• 구간 합 알고리즘 구현: sum[] 배열을 사용
  -> sum[i]: 현재 인덱스i 까지의 총 합 저장
  -> sum[i] = sum[i-1] + arr[i]