백준) 3032 승리(IVANA)

3032. 승리

문제

상근이의 여동생 선영이는 정인이가 상근이의 마이크로프로세서를 훔치는 것을 보았다. 선영이는 상근이에게 이 사실을 말해야 하는지를 고민했다. 하지만, 선영이는 상근이보다 정인이를 더 좋아하기 때문에 말하지 않았다.

선영이는 정인이에게 데이트 신청을 하였고, 영화를 같이 보러간다면 이 사실을 그 누구에게도 말하지 않기로 약속했다.

알고보니 정인이는 여자에게 별 관심이 없었다. 그 이유는 정인이가 수학문제를 푸는데 방해 된다고 생각하기 때문이다.

따라서, 그는 선영이에게 게임을 신청했고, 이기면 영화를 보러 가기로 했다.

선영이는 게임에 자신이 있었기 때문에, 정인이의 제안에 동의했다.

정인이는 N개의 양수를 원 위에 차례대로 쓰고 선영이에게 게임의 규칙을 설명했따.

1. 첫 번째 플레이어가 아무 숫자나 하나 고른다.

2. 두 번째 플레이어가 첫 번째 플레이어가 고른 수에 인접한 두 수 중 하나를 고른다.

3. 그 다음 플레이어는 고를 수 있는 수가 없을 때까지 지금까지 고른 수에 인접한 수 중에서 아무 숫자나 고른다.

4. 홀수를 가장 많이 고른 사람이 승리한다.

정인이는 최선을 다해서 게임을 한다. 그는 항상 이기거나 비길 수 있는 전략을 선택한다.

정인이는 선영이가 게임을 얼마나 잘 하는지 모른다. 또, 정인이는 신사이기 때문에, 선영이에게 첫 번째 수를 양보했다.

선영이가 게임을 승리하기 위해서 고를 수 있는 첫 번째 수의 총 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 원 위에 있는 수의 개수 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 모든 숫자는 1 이상 1000 이하이다. 두 수가 같은 경우는 없다.

출력

선영이가 게임을 승리하기 위해서 고를 수 있는 첫 번째 수의 개수를 첫째 줄에 출력한다.

예제 입력 

3
3 1 5

예제 출력 

3

1. 접근

두 게이머가 게임을 한다.

다만 두 명 모두 최선의 전략을 구사할 줄 알고(근데 우리는 모른다) 게임에 임할 때,

첫 순서인 플레이어가 이길 수 있는 경우의 수를 묻는 문제다.

역시나 짱구를 굴려봐도 최선의 전략이 뭔지 모르겠으니까, 모든 경우를 시도해보는(하지만 빠른) 다이나믹 프로그램을 써보자.

고려할 점은 n개의 수가 일렬로 있는게 아니라 원형 배열에 있다는 점이다.

2. 풀이

처음의 선택으로 원형배열은 일렬의 배열로 바뀐다. 선택의 양쪽 수가 배열의 양쪽 끝 수가 될 것이다.

 

그러면 카드게임 : http://js1jj2sk3.tistory.com/33 의 경우와 같아진다.

이기기 위한 전략이 뭔지는 모르겠지만, 나의 점수를 최대한으로 하려는 것이다. (상대의 점수를 최소한으로 하려는 것이다)

다만 문제가 요구하는 것은 첫 번째 선택으로 올바른 경우를 세야 하므로 지금까지의 turn을 고려하는 함수는 만들기 어렵다.

(내 머리로 못함)

func(int x, int y) = 남은 배열(입력받은 배열)이 x부터 y일때, 낼 수 있는 최대한의 점수차이.

위와 같이 정의한다면 현재 순서가 누구인지 고려할 필요가 없다.

기저사례는 x==y인 경우로, 입력의 x번째 수가 홀수라면 1, 아니면 0을 리턴해주자.

이제 왼쪽을 고르거나 오른쪽을 고르는 경우를 모두 계산해주면 된다!

한 쪽을 고를 때 만들 수 있는 최대한의 점수차이는 어떻게 기술해야 할까?

한 쪽을 고르고 얻은 점수 - 나머지로 만드는 최대한의 점수 차이 = 한 쪽을 고르면 얻는 최대한의 점수차이

int left = func(x, x) - func((x + 1) % n, y);

int right = func(y, y) - func(x, (y + n - 1) % n);

라고 쓸 수 있다.

이걸 이해하는게 개인적으로 엄청 힘들었다 (멍청). 이번엔 턴을 고려하지 않는다.

내 턴이라 생각해보면, 선택 이후 턴이 넘어가기 때문에, 당연히 상대방은 최선의 전략을 구사하므로 함수를 호출하신다.

상대가 만드는 점수차는 당연히 내 점수에서 까야 된다.

왼쪽을 선택해서 만드는 점수차는 1점 - 3점차 = -2점차가 된다.

답은 어떻게 고를까? 내가 한 지점을 고르고 먹는 점수와, 상대방이 나머지로 만들 수 있는 최대 점수차를 비교해보면 된다.

func(i, i) - func((i + 1) % n, (i + n - 1) % n) > 0

이라면 내가 이긴다.

3. 코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[101][101];
int n, t, i;
int func(int x, int y) {
	if (x == y) 
		return dp[x][y];
		
	if (dp[x][y] != -1)
		return dp[x][y];
	int left = func(x, x) - func((x + 1) % n, y);
	int right = func(y, y) - func(x, (y + n - 1) % n);
	return dp[x][y] = max(left, right);
}
int main() {
	scanf("%d", &n);
	memset(dp, -1, sizeof(dp));
	for (i = 0; i < n; ++i) {
		scanf("%d", &dp[i][i]);
		dp[i][i] %= 2;
	}
	
	int ans = 0;
	for (i = 0; i < n; ++i)
		if (func(i, i) > func((i + 1) % n, (i + n - 1) % n))
			ans++;
	printf("%d", ans);
	return 0;
}