Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 푸는 숫자 추측하기 II — 미니맥스 DP로 최소 비용 구하기

문제 소개: 숫자 추측 게임 II

두 명의 플레이어가 '숫자 추측 게임(Guess Game)'을 한다고 가정해 보겠습니다. 게임 규칙은 다음과 같습니다.

  • 플레이어 1이 1부터 n 사이의 숫자 하나를 몰래 고릅니다.
  • 플레이어 2는 플레이어 1이 고른 숫자를 맞혀야 합니다.
  • 플레이어 2가 틀릴 때마다, 플레이어 1은 정답이 선택한 숫자보다 높은지 낮은지 힌트를 줍니다.

여기에 중요한 조건이 하나 있습니다. 플레이어 2가 특정 숫자 x를 추측했는데 틀리면, 그 즉시 x달러를 지불해야 합니다. 게임은 플레이어 2가 정답을 맞히는 순간 종료됩니다.

예시로 이해하기

n = 10이고, 플레이어 1이 8을 골랐다고 가정해 봅시다.

  • 첫 번째 라운드: 플레이어 2가 5를 말함 → 오답, 실제 숫자가 더 높음 → $5 지불
  • 두 번째 라운드: 플레이어 2가 7을 말함 → 오답, 실제 숫자가 더 높음 → $7 지불
  • 세 번째 라운드: 플레이어 2가 9를 말함 → 오답, 실제 숫자가 더 낮음 → $9 지불

이후 정답을 맞히며 게임이 끝나고, 총 지불 금액은 5 + 7 + 9 = $21이 됩니다.

이 문제의 목표는 단순히 정답을 맞히는 것이 아니라, 정답을 반드시 맞힌다는 전제 아래 최악의 경우에도 지불해야 할 금액을 최소화하는 것입니다. 어떤 순서로 숫자를 추측해야 손실을 최소로 줄일 수 있을지 찾아야 합니다.

접근 방법: 미니맥스(Minimax) + 동적 계획법

이 문제는 대표적인 미니맥스 최적화 유형입니다. 구간 [low, high]에 대해 다음과 같이 정의합니다.

  • cost(low, high): 정답이 [low, high] 범위 안에 있을 때, 최적의 전략으로 진행했을 경우 최악의 상황에서 지불하게 되는 최소 금액

구간 내 임의의 숫자 i를 추측한다면 결과는 두 가지입니다.

  • 정답을 맞히면 게임이 끝나므로 추가 비용이 없습니다.
  • 틀리면 i달러를 지불하고, 정답은 왼쪽 구간 cost(low, i−1) 또는 오른쪽 구간 cost(i+1, high) 중 한곳에 있습니다. 최악의 경우를 대비해야 하므로 두 값 중 더 큰 값을 선택해야 합니다.

이를 점화식으로 표현하면 다음과 같습니다.

cost(low, high) = min { i + max(cost(low, i-1), cost(i+1, high)) }  (단, low ≤ i ≤ high)

알고리즘 단계

  1. low, high, 그리고 메모이제이션 테이블 dp를 인자로 받는 cost 함수를 생성합니다.
  2. low ≥ high이면 추측할 숫자가 없거나 하나뿐이므로 0을 반환합니다.
  3. dp[low][high]가 이미 계산된 값(-1이 아닌 값)이라면 그대로 반환합니다.
  4. ans를 INT_MAX(무한대)로 초기화합니다.
  5. i를 low부터 high까지 순회하면서 ans = min(ans, i + max(cost(low, i−1), cost(i+1, high)))로 갱신합니다.
  6. dp[low][high]에 ans를 저장한 뒤 반환합니다.

메인 함수에서는 (n+1) × (n+1) 크기의 2차원 배열 dp를 만들어 −1로 초기화한 후, cost(1, n, dp)를 호출하면 됩니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int cost(int low, int high, vector < vector <int> >& dp){
        if(low >= high)return 0;
        if(dp[low][high] != -1)return dp[low][high];
        int ans = INT_MAX;
        for(int i = low; i <= high; i++){
            ans = min(ans, i + max(cost(low, i - 1, dp), cost(i + 1, high, dp)));
        }
        return dp[low][high] = ans;
    }
    int getMoneyAmount(int n) {
        vector < vector <int> > dp(n + 1, vector <int> (n + 1, -1));
        return cost(1, n, dp);
    }
};
int main() {
    Solution ob1;
    cout << ob1.getMoneyAmount(8) << endl;
    return 0;
}

실행 결과 확인

입력

8

출력

12

n = 8일 때 최적의 전략으로 게임을 진행하면, 최악의 경우에도 지불 금액을 $12로 제한할 수 있다는 의미입니다.

복잡도 분석

  • 시간 복잡도: O(n³) — 구간의 개수가 O(n²)개이고, 각 구간마다 최대 n번의 추측 후보를 검사합니다.
  • 공간 복잡도: O(n²) — 모든 구간의 결과를 저장하는 2차원 dp 테이블이 필요합니다.