예제: 숫자 게임
n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있습니다.
- 게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다.
- 게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지웁니다.
게임은 모든 숫자가 다 없어졌을 때 끝나며, 각 사람의 점수는 자신이 가져간 숫자들의 합입니다. 현우와 서하는 점수가 더 낮은 쪽이 점수 높은 쪽에 한 점 차이마다 백 원씩 주기로 내기를 했습니다. 두 사람 모두 최선을 다할 때, 두 사람의 최종 점수 차이는 얼마일까요?
입력
입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 이 주어집니다. 각 테스트 케이스의 첫 줄에는 게임판의 길이 n (1 <= n <= 50) 이 주어지며, 그 다음 줄에 n 개의 정수로 게임판의 숫자들이 순서대로 주어집니다. 각 숫자는 -1,000 에서 1,000 사이의 정수입니다.출력
각 테스트 케이스마다 한 줄로, 두 사람이 최선을 다했을 때 현우가 서하보다 몇 점 더 얻을 수 있는지를 출력합니다.예제 입력
3 5 -1000 -1000 -3 -1000 -1000 6 100 -1000 -1000 100 -1000 -1000 10 7 -5 8 5 1 -4 -8 6 7 9예제 출력
-1000 1100 7
풀이
알고리즘 문제해결 전략을 통해 동적 계획법 문제를 여러 개 풀어 보았지만, 저번에 풀었던 TICTACTOE나 NUMBERGAME과 같은 조합 게임(combinatiorial game)은 아직 어색한 것 같다.
다음 재귀 함수가 현재 게임판의 state를 관리한다는 것과, 플레이어 턴이 재귀함수를 호출할때마다 바뀐다는것을 명심해야겠다.
이번 문제에서, 재귀함수를 호출함으로써 불러오는 다음 상태는 상대방의 최대 값이 되므로, 현재 함수에서 구현해야 할 로직은 다음과 같다.
result = max(case1, case2, case3, case4);
case를 하나씩 살펴보자.
-
case1 : 현재 사용자가 왼쪽 끝(left)에서의 수를 택한 경우
case1 = board[left] - next_state(left + 1, right);
여기서 -를 해 주는 이유는 두 플레이어의 점수의 차를 리턴해야 하기 때문이다. -
case2: 현재 사용자가 오른쪽 끝(right)에서의 수를 택한 경우
case2 = board[right] - next_state(left, right - 1);
case1과 유사하다. -
case3: 왼쪽 끝 숫자를 두 개 삭제한 경우
case3 = -next_state(left + 2, right);
왼쪽 끝 숫자를 두 개 삭제하였으므로, 현재 플레이어가 가져갈 점수는 없다. -
case4: 왼쪽 끝 숫자를 두 개 삭제한 경우
case4 = -next_state(left, right - 2);
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<algorithm>
using namespace std;
const int NEGINF = -987654321;
int n;
int board[50];
int cache[50][50];
//현재 player의 점수 최대치를 반환
int numberGame(int left, int right) {
if (left == right) return board[left];
if (left > right) return 0;
int& res = cache[left][right];
if (res != NEGINF) return res;
//case 1
res = board[left] - numberGame(left + 1, right);
//case 2
res = max(res, board[right] - numberGame(left, right - 1));
if (right - left >= 2) {
//case 3
res = max(res, -numberGame(left + 2, right));
//case 4;
res = max(res, -numberGame(left, right - 2));
}
return res;
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
for (int i = 0; i < 50; i++) {
for (int j = 0; j < 50; j++) {
cache[i][j] = NEGINF;
}
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> board[i];
}
cout << numberGame(0, n - 1) << endl;
}
return 0;
}풀이 후기
알고리즘을 풀면 풀 수록 현실세계에서 접근하는 방식과는 참 다르다는것을 많이 느낀다.
필자만 그런지 모르겠지만, 시간에 흐름에 따라 살아서 그런지 모든 문제를 시간의 흐름에 따라 생각하려는 성향이 강하다. 그래서 많은 사람들이 객체지향보다 절차지향에 익숙한 것이 아닐까.
얼른 내가 알파고다! 내가 컴퓨터다! 하는 느낌으로 문제 접근방식을 바꿔야겠다.
