[ 백준 11062] 카드 게임(C++)

 

11062번: 카드 게임

 

 

문제!

---

근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다.

근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오.

예를 들어 카드가 [4, 3, 1, 2]로 놓여있다고 하자. 근우는 처음에 4가 적힌 카드를 가져가고, 명우는 3이 적힌 카드를 가져간다. 그리고 근우는 2가 적힌 카드를 가져가고, 명우는 마지막으로 1이 적힌 카드를 가져간다. 이때 근우와 명우는 최선의 전략으로 임했으며, 근우가 얻는 점수는 6이다.

 

---

요약하면 근우와 명우가 양 끝의 카드를 한장씩 선택하는 게임을 하는데 근우가얻는 최대 점수를 구하는 문제!

 

 

 

먼저 생각해보아야할것은

1. 무작정 숫자가 큰 카드를 고르는것은 답이 될수없다.

2. 게임에서 한쪽이 점수를 최대로 받으려면 다른한쪽은 점수를 최하로 받아야한다

 

이정도만....?

 

 

처음에는 완전탐색을 통해 풀어볼려했으나

양쪽중 어느곳을 선택한다 쳤을때 카드의 최대수가 1000장이니

 

2의 500승...?

절대 안되죠

 

이럴때마다 사용하는 방법이 dp!

 

 

dp[L][R] ==> 왼쪽끝, 오른쪽 끝   

dp 에는 근우의 점수를 넣어줍시다.

 

이런식으로 저장해보겠습니다.

 

 

시작!

---

먼저 평범하게 입력을 받고

int main() {
	
	cin >> T;
		
	while (T--) {
		
		cin >> n;

		v.resize(n, 0);
		for (int i = 0; i < n; i++) {
			cin >> v[i];
		}

		cal(0, n - 1, 1);
		cout<<dp[0][n-1]<<endl;

		memset(dp, 0, sizeof(dp));
	} 


	return 0;
	
}

 

 

 

다음은 탐색하는 부분입니다.

int cal(int l,int r, bool turn) {
	if (l > r) {// 한장 남음
		return 0;
	}

	if (dp[l][r]) {// 계산한 값이 있음
		return dp[l][r];
	}

	

	if (turn) {//카드 선택
		return dp[l][r] = max(cal(l, r - 1, !turn) + v[r], cal(l + 1, r, !turn) + v[l]);
	}
	else {
		return dp[l][r] = min(cal(l, r - 1, !turn), cal(l + 1, r, !turn));// 이쪽은 항상작게
	}
}

 

값이 있다면 그 값을 리턴!

왼쪽끝과 오른쪽끝이 같으면 현재값을 리턴

나머지는 양쪽중 한쪽을 선택해 나가면서 최댓값을 저장해줍시다!

(근우 순서가 아닐때는 최소를 선택하는것처럼)

 

 

그러면 끝!

 

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

vector <int>  v;
int T, n;
int count = 0;

int dp[1001][1001];


int cal(int l,int r, bool turn) {
	if (l > r) {// 한장 남음
		return 0;
	}

	if (dp[l][r]) {// 계산한 값이 있음
		return dp[l][r];
	}

	

	if (turn) {//카드 선택
		return dp[l][r] = max(cal(l, r - 1, !turn) + v[r], cal(l + 1, r, !turn) + v[l]);
	}
	else {
		return dp[l][r] = min(cal(l, r - 1, !turn), cal(l + 1, r, !turn));// 이쪽은 항상작게
	}
}


int main() {
	
	cin >> T;
		
	while (T--) {
		
		cin >> n;

		v.resize(n, 0);
		for (int i = 0; i < n; i++) {
			cin >> v[i];
		}

		cal(0, n - 1, 1);
		cout<<dp[0][n-1]<<endl;

		memset(dp, 0, sizeof(dp));
	} 


	return 0;
	
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!