[BOJ 백준] 카드 게임 (11062) Java

링크 : https://www.acmicpc.net/problem/11062

 

문제 설명 : 

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

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

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

 

입력 :

입력의 첫 줄에는 테스트케이스의 수 T가 주어진다.

각 테스트케이스 마다 첫 줄에는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N개의 자연수가 공백으로 구분되어 주어지는데, i번째로 주어지는 수는 왼쪽에서 i번째에 놓인 카드에 적힌 수를 의미한다. 카드에 적혀있는 수는 1이상 10,000이하다.

 

출력 : 

각 테스트케이스마다 근우와 명우가 최선의 전략으로 임할 때 근우가 얻게되는 점수를 줄로 구분하여 출력한다.

 

예제 입력 : 

2

4

1 2 5 2

9

1 1 1 1 2 2 2 2 2

 

예제 출력 : 

6

8

 

접근법 : 

1) 어떻게 풀 것인가?

N이 1,000으로 크지 않아 O(N^2)은 여유있어 보인다.

 

예제로 주어진 초기 카드 세팅을 보면 가장 오른쪽 카드(2)를 가져갈 경우

카드가 이렇게 남고

 

가장 왼쪽 카드(1) 을 가져갈 경우

카드가 이렇게 남는다.

 

 

즉, 두 플레이어가 하는 선택이 다른 플레이어의 선택에 영향을 미친다.

문제 조건 중에 두 플레이어 모두 최선의 전략으로 게임에 임한다는 조건이 있어서,

분할정복 방식으로 모든 케이스를 해보기로 했다.

 

이때 구현한 함수는 아래와 같다.

	// 출발, 도착, flag 0 근우, 1 명우
	static int cardGame(int start, int end, int flag) {

		// 1. 마지막 카드라면
		if (start == end) {
			// 1-1. 근우 차례면
			if (flag == 0) {
				return dp[flag][start][end] = input[start];
			}
			// 1-2. 명우 차례면
			else {
				return dp[flag][start][end] = 0;
			}
		}

		// 2. 이미 알고 있으면 가지치기
		if (dp[flag][start][end] != 0)
			return dp[flag][start][end];

		// 3. 게임 진행을 통해 값을 알아야하면 분할정복 진행
		// 3-1. 근우 차례면
		if (flag == 0) {
			dp[flag][start][end] = Math.max(cardGame(start + 1, end, 1) + input[start], cardGame(start, end - 1, 1) + input[end]);
		}
		// 3-2. 명우 차례면
		else {
			dp[flag][start][end] = Math.min(cardGame(start + 1, end, 0), cardGame(start, end - 1, 0));
		}
		return dp[flag][start][end];
	}

 

주석이 있어 길어보이지만 주요 로직은

① 기저면까지 왔을때 ( start = end) 

② dp[ ] [ ] [ ] 배열에 값이 들어와있을때 가지치기

③ 서로의 턴에서 최선의 선택을 하고 재귀호출 하기 

 

전체 코드는 아래 참고.

 

2) 시간복잡도

O(N^2)으로 무리 없음

(Java 기준 - 496ms)

 

3) 공간복잡도

N이 1,000으로 N*N*2 3차원 배열 만들어도 무리 없다.

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

분할정복 코드 작성법

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 11062 카드 게임 
public class Main {

	static int T, N; // T - 테스트케이스 개수, N 카드 개수
	static int[] input;
	static int[][][] dp; // dp [ 0 근우, 1 명우 ] [ 출발범위 ] [ 도착범위 ]

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			// 1. 입력받기
			N = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());

			input = new int[N + 1];
			for (int i = 1; i <= N; i++) {
				input[i] = Integer.parseInt(st.nextToken());
			}

			dp = new int[2][N + 1][N + 1];
			int ans = cardGame(1, N, 0);

			bw.write(ans+"\n");
		}

		bw.flush();
		bw.close();
		br.close();
	}

	// 출발, 도착, flag 0 근우, 1 명우
	static int cardGame(int start, int end, int flag) {

		// 1. 마지막 카드라면
		if (start == end) {
			// 1-1. 근우 차례면
			if (flag == 0) {
				return dp[flag][start][end] = input[start];
			}
			// 1-2. 명우 차례면
			else {
				return dp[flag][start][end] = 0;
			}
		}

		// 2. 이미 알고 있으면 가지치기
		if (dp[flag][start][end] != 0)
			return dp[flag][start][end];

		// 3. 게임 진행을 통해 값을 알아야하면 분할정복 진행
		// 3-1. 근우 차례면
		if (flag == 0) {
			dp[flag][start][end] = Math.max(cardGame(start + 1, end, 1) + input[start], cardGame(start, end - 1, 1) + input[end]);
		}
		// 3-2. 명우 차례면
		else {
			dp[flag][start][end] = Math.min(cardGame(start + 1, end, 0), cardGame(start, end - 1, 0));
		}
		return dp[flag][start][end];
	}
}