[BOJ] 백준 10835번 : 카드게임 (JAVA)
문제
지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.
이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.
- 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
- 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
- (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개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.
출력
얻을 수 있는 최종 점수의 최댓값을 출력한다.
풀이
다이나믹 프로그래밍으로 해결할 수 있는 문제였습니다.
카드를 버리는 경우는 총 3가지였습니다.
첫 번째는 "왼쪽 카드만 버리기", 두 번째는 "왼쪽, 오른쪽 카드 버리기", 세 번쨰는 "오른쪽 카드 버리기"입니다.
여기서, 세 번째 케이스는 반드시 왼쪽 카드보다 숫자가 작아야한다는 제약이 있었습니다.
메모이제이션을 통한 Top-down 방식을 이용하여 위의 3가지 케이스를 그대로 재귀 함수에 적용하시면 됩니다.
아래 소스코드를 참고하시길 바랍니다.
소스코드
지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.
'PS > 백준' 카테고리의 다른 글
[BOJ] 백준 2600번 : 구슬게임 (JAVA) (0) | 2020.09.20 |
---|---|
[BOJ] 백준 16888번 : 루트 게임 (JAVA) (0) | 2020.09.20 |
[BOJ] 백준 4811번 : 알약 (JAVA) (0) | 2020.09.18 |
[BOJ] 백준 2056번 : 작업 (JAVA) (0) | 2020.09.15 |
[BOJ] 백준 13398번 : 연속합 2 (JAVA) (0) | 2020.09.15 |
댓글