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

#10835 카드게임 

난이도 : 실버 1

유형 : DP

 

10835번: 카드게임

▸ 문제

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다. 

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다

카드 순서	왼쪽 더미	오른쪽 더미
1	3	2
2	2	4
3	5	1

이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다.

두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최댓값은 7이다.

 

▸ 입력

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1 ≤ B ≤ 2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.

▸ 출력

얻을 수 있는 최종 점수의 최댓값을 출력한다.

 

 

 

문제 풀이 

DP문제를 풀 때 항상 고민하는 것은 'Top-down으로 풀어야하나 Bottom-up으로 풀어야하나' 이다. 그래서 다른 사람들은 어떻게 사용하는지 좀 찾아봤다. (링크)

[알고리즘] DP문제에서 Top-down과 Bottom-up 어떻게 판단할까?

 

여러 글들을 종합해본 결과 DP 풀이 접근 방식은 Top-down이 자연스럽게 접근이 가능하지만 효율성을 고려해야할 경우는 Bottom-up이 더 좋다.

 

보통 나는 Top-down이 더 접근이 용이하다. 특히 이러한 카드게임같은 문제는 더더욱.

가끔 숫자로 장난치는 문제는 Bottom-up이 더 접근하기 쉬울때도 있다.

 

그래서 앞으로 나의 dp풀이는 전반적으로 Top-down으로 문제를 읽어보고 하위문제가 너무 간단하다고 판단될 경우 Bottom-up으로 방향으로 바꾸는 방식으로 풀이를 해야겠다.

 

(근데 풀이해보고나니 재귀호출을 하긴했지만 Bottom-up 접근 방식인 것 같다...)

 

 

▸ 풀이 과정

left[], right[] 배열에 각 카드 더미를 저장해놨다. index+1을 하면 해당 index카드를 버렸다고 가정해도 된다.

 

점수를 얻는 경우는 단 하나, 왼쪽 카드가 오른쪽 카드보다 더 클 경우이다. 해당 조건에서만 count를 해주면 된다.

 

카드의 움직임 종류는 세가지이다.

   1. 왼쪽, 오른쪽 

   2. 왼쪽만

   3. if(왼쪽 > 오른쪽) 오른쪽만 -> 점수+

 

 

 

풀이 코드 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int n;
	static int[] left;
	static int[] right;
	static int[][] dp;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		left = new int[n];
		right = new int[n];
		for(int i =0; i<n; i++) {
			left[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i =0; i<n; i++) {
			right[i] = Integer.parseInt(st.nextToken());
		}
		
		dp = new int[n][n];
		for(int i=0; i<n; i++) {
			Arrays.fill(dp[i], -1);
		}
 
		System.out.println(Topdown(0,0));
	}
	
	static int Topdown(int l, int r) {
		if(l == n || r == n) return 0;
		
		if(dp[l][r] != -1) return dp[l][r];
		
		// l+1, r+1 : 양쪽 카드를 동시에 제거하는 경우
		// l+1, r : 왼쪽 카드만 제거하는 경우 
		dp[l][r] = Math.max(Topdown(l+1, r+1), Topdown(l+1, r));
		
		if(left[l] > right[r]) {
			dp[l][r] = Math.max(dp[l][r], Topdown(l, r+1)+right[r]);
		}
		return dp[l][r];
	}
}