숫자게임
[algospot, 난이도하, c++]
출력해야 하는 값은 현우가 서하보다 몇 점 더 얻을 수 있는지다. 그래서 현우-서하 가 최대인 값을 출력하는 함수를 생각했다.
현주-서하 함수이름();
메모라이즈 할 수 있는 좋은 파라미터를 생각해봤을때, 범위 값을 생각했다.
구현 자체는 어렵지 않았는데, 몇가지 돌아볼 점이 있다면,
- 지금이 현우인지 서하 인지에 따라서 max 인지 min 가 바뀐다.
- 이게 알고보니 인공지능 과목에서 배우는 미니맥스 알고리즘 이란다.
- 사실 더 최적화된 답이 있었는데, turn 파라미터를 제거해도 가능한 답이다.
( 현재 게임판에 남은 수들이 [s..e)일 때 (이번 차례인 참가자의 점수 - 다른 참가자의 점수)의 최대치 )
- max 나 min 을 쓸 때, 초기화를 특정 수로 하지말고 함수 결과로 바로 넣기
max(maxScoreDiff(board, s + 2, e, false), maxRet, maxScoreDiff(board, s, e - 2, false))
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int cache[51][51][2];
// 범위[s..e)와 누구 차례(1, 0)인지 주어졌을때 현우와 서하의 점수 차 의 최대값을 반환한다.
int maxScoreDiff(vector<int> &board, int s, int e, bool turn) {
// 기저사례
// 1. 하나 남았다.
if (s + 1 == e) {
if (turn) { // 현우 차례면
return board[s];
} else { // 서하 차례면
return -board[s];
}
}
// 2. 끝
if (s == e) {
return 0;
}
// 메모이제이션
int &ret = cache[s][e][turn ? 1 : 0];
if (ret != -1000000000) return ret;
// 현우 차례일때
if (turn) {
int maxRet = -1000000000;
// 왼쪽을 가져온다.
maxRet = max(maxRet, board[s] + maxScoreDiff(board, s + 1, e, false));
// 오른쪽을 가져온다.
maxRet = max(maxRet, board[e - 1] + maxScoreDiff(board, s, e - 1, false));
// 왼쪽 2개를 지운다.
maxRet = max(maxRet, maxScoreDiff(board, s + 2, e, false));
// 오른쪽 2개를 지운다.
maxRet = max(maxRet, maxScoreDiff(board, s, e - 2, false));
return ret = maxRet;
} else {
int minRet = 1000000000;
// 왼쪽을 가져온다.
minRet = min(minRet, -board[s] + maxScoreDiff(board, s + 1, e, true));
// 오른쪽을 가져온다.
minRet = min(minRet, -board[e - 1] + maxScoreDiff(board, s, e - 1, true));
// 왼쪽 2개를 지운다.
minRet = min(minRet, maxScoreDiff(board, s + 2, e, true));
// 오른쪽 2개를 지운다.
minRet = min(minRet, maxScoreDiff(board, s, e - 2, true));
return ret = minRet;
}
}
void numbergame() {
int c;
cin >> c;
for (int test_case = 0; test_case < c; ++test_case) {
int n;
cin >> n;
vector<int> board(n);
for (int i = 0; i < n; ++i) {
cin >> board[i];
}
for (auto &i: cache) {
for (auto &j: i) {
for (int &k: j) {
k = -1000000000;
}
}
}
// 현우(true) 부터 시작
cout << maxScoreDiff(board, 0, n, 1) << endl;
}
}