취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15490번 문제인 즐거운 게임이다.
문제는 아래 링크를 확인하자.

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

주어진 배열의 각 연속한 부분배열 [L,R]과 현재 게임 진행상황(kcm1700이 지금까지 고른 수의 합의 홀짝여부와 다음 진행할 차례가 누구인지의 여부)에 대한 부분문제를 생각할 수 있다. 이러한 부분문제의 풀이를 이용해 dp로 문제를 해결하자. 이러한 dp는 다차원 배열을 이용해 진행해나갈 수 있다.

kcm1700의 차례에는 어느 한 방향으로라도 kcm1700이 이길 수 있는 방향이 존재한다면 이길 수 있는 것이고, ntopia의 차례에는 어느 한 방향으로라도 ntopia가 이길 수 있는 방향이 존재한다면 kcm1700이 이길 수 없다는 점을 잘 이용해 구현해주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
bool arr[3000];
bool dp[3000][3000][2][2];
bool visited[3000][3000][2][2]; // turn = 1: ntopia 차례
// dp[L][R][odd/even][turn]
// 현재 남은 구간은 [L,R]
// 내가 합한 수들이 홀수이면 odd/even = 1, 짝수이면 odd/even = 0
// 지금 차례인 사람이 kcm1700이면 turn = 0, ntopia이면 turn = 1
// 이 상황에 대하여 kcm1700이 이길 수 있는 방법이 존재하면 dp배열에 1을 저장, 그렇지 않다면 0을 저장

bool func(int L, int R, int odd, int turn) {
	auto& ptr = dp[L][R][odd][turn];
	if (visited[L][R][odd][turn]) return ptr;
	visited[L][R][odd][turn] = 1;
	
	if (L == R) {
		if (turn) return ptr = !odd;
		else if (arr[L]) return ptr = odd;
		else return ptr = !odd;
	}
	else if (L + 1 == R) {
		if (turn) {
			ptr = 1;
			ptr &= func(L + 1, R, odd, turn ^ 1);
			ptr &= func(L, R - 1, odd, turn ^ 1);
			ptr &= !odd;
		}
		else {
			int cnt = 0;
			if (arr[L]) cnt ^= 1;
			ptr |= func(L + 1, R, odd ^ cnt, turn ^ 1);
			if (arr[R]) cnt ^= 1;
			ptr |= !(odd ^ cnt);
			if (arr[L]) cnt ^= 1;
			ptr |= func(L, R - 1, odd ^ cnt, turn ^ 1);
		}

		return ptr;
	}

	if (turn) {
		ptr = 1;
		ptr &= func(L + 1, R, odd, turn ^ 1);
		ptr &= func(L + 2, R, odd, turn ^ 1);
		ptr &= func(L, R - 1, odd, turn ^ 1);
		ptr &= func(L, R - 2, odd, turn ^ 1);
	}
	else {
		int cnt = 0;
		if (arr[L]) cnt ^= 1;
		ptr |= func(L + 1, R, odd ^ cnt, turn ^ 1);
		if (arr[L + 1]) cnt ^= 1;
		ptr |= func(L + 2, R, odd ^ cnt, turn ^ 1);
		cnt = 0;
		if (arr[R]) cnt ^= 1;
		ptr |= func(L, R - 1, odd ^ cnt, turn ^ 1);
		if (arr[R - 1]) cnt ^= 1;
		ptr |= func(L, R - 2, odd ^ cnt, turn ^ 1);
	}

	return ptr;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		arr[i] = x & 1;
	}

	if (func(0, N - 1, 0, 0)) cout << "Yes";
	else cout << "No";
}