[백준 c++] 11062 카드게임

[문제]

https://www.acmicpc.net/problem/11062

 

-근우(선발 주자)와 명우(후발 주자)가 가장 왼쪽이나 오른쪽 카드를 가져간다.

-최종적으로 근우가 큰 값을 가지도록 했을 때, 근우의 점수를 구하는 것이 목표.

 

[문제 쪼개기]

-큰 문제를 작은 문제로 쪼개보자.

큰 문제는 '모든 카드에서 최선의 선택'을 하는 것이다. 그런데 남아있는 카드가 [1, 2, 5, 2]라면, 근우는 첫 번째 카드를 가져갈지, 마지막 카드를 가져갈지 선택을 해야만한다.

 

① 카드가 1장 있을 때 

A

 

근우가 A을 가지고 간다.

근우 A점, 명우 0점

 

② 카드가 2장 있을 때

 

A

B

근우는 고민없이 max(A, B) 값을 가지고 간다.

 

③ 카드가 3장 있을 때

A

B

C

근우가 A를 가져가면, 명우는 B,C 중에서 큰 값을 가지고 간다.

근우가 C를 가져가면 명우는 A,B 중에서 큰 값을 가지고 간다.

 

d[i][j] 는 i 번째 카드부터 j번째 카드까지 남아있을 때, 근우가 최적의 전략으로 얻을 수 있는 최대 점수를 의미한다.

 

1) 왼쪽에서 카드 선택

i 번째 카드를 선택하면, 근우는 cards[i]를 얻고, 명우는 [i+1, j] 구간에서 최적의 선택이 된다.

근우가 첫 번째 카드를 선택했을 때 최종 점수는,

cards[i] + (남은 카드에서 명우가 얻을 점수를 제외한 값)이 됩니다.

즉, dp[i][j] = cards[i] + (전체 점수 - dp[i+1][j])

 

2) 오른쪽에서 카드 선택

j 번째 카드를 선택하면, 근우는 cards[j]를 얻고, 명우는 [i, j-1] 구간에서 최적을 선택을 하게 된다.

즉, dp[i][j] = cards[i] + (전체 점수 - dp[i][j-1])

 

3) 최종 점화식

dp[i][j] = max(cards[i] + (전체 점수 - dp[i+1][j]), cards[j] + (전체 점수 - dp[i][j-1]))

 

=> 실제로 코드 쓸 때는, 내 점수를 현재 카드 점수 + min(근우가 왼쪽 카드 선택하고 남은 점수, 근우가 오른쪽 카드 선택하고 남은 점수) 로 계산함.

 

C++전체 코드

1. 위 로직대로, 전체 점수에서 명우가 더 큰 값을 가져간다는 로직

#include <iostream>
#include <vector>
#include <cstring> //memset

using namespace std;

int dp[1001][1001]; //dp테이블 정의
int sum[1001]; //카드 점수의 누적 합을 저장

//점수 계산을 위한 함수
int getMaxScore(vector<int>& cards, int left, int right) {
    //기저 조건 : 만약 left 가 right를 넘어서면, 유효하지 않은 범위이므로 0변환
    if (left > right) return 0;
    
    //이미 계산된 값이 있으면 그 값을 사용
    if (dp[left][right] != -1) return dp[left][right];
    
    //전체 카드의 총합 중에서, 상대방이 최선의 선택을 해서 얻을 수 있는 점수를 뺀 값을 계산
    int totalSum = sum[right + 1] - sum [left];
    int pickLeft = totalSum - getMaxScore(cards, left+1, right);
    int pickRight = totalSum - getMaxScore(cards, left, right-1);
    
    //두 경우 중 최대값을 DP 테이블에 저장
    return dp[left][right] = max(pickLeft, pickRight);
    
}

int main() {
    int T;
    cin >> T;
    
    while(T--) {
        //각 카드 점수 입력
        int N;
        cin >> N;
        vector<int> cards(N);
        for (int i=0; i<N; i++){
            cin >> cards[i];
        }
        
        //DP테이블을 -1로 초기화
        memset(dp, -1, sizeof(dp));
        
        //카드 점수의 누적 합 계산
        sum[0]=0;
        for (int i=0; i<N; i++){
            sum[i+1] = sum[i] + cards[i];
        }
        
        //0번부터 N-1번까지 카드가 있을 때 근우가 얻는 최대 점수 계산
        cout << getMaxScore(cards, 0, N-1) << endl;
    }
    return 0;
}

2. 명우가 둘 중에 더 작은 것을 가져간다는 로직으로 짠 코드

#include <iostream>
#include <vector>
#include <cstring> //memset을 사용하기 위해

using namespace std;

int dp[1001][1001]; //dp table 정의

//점수 계산을 위한 함수

int getMaxScore(vector<int>& cards, int left, int right) {
    
    //기저조건 : 만약 left가 right를 넘어서면, 유효하지 않은 범위이므로 0반환
    if (left > right ) return 0;
    
    //기저조건 : 만약 왼쪽=오른쪽이 같으면, 카드가 하나 남았다는 의미
    if (left == right) return cards[left];
    
    //이미 계산된 값이 있으면 그 값 사용
    if (dp[left][right] != -1) return dp[left][right];
    
    //왼쪽을 선택하는 것은 = 준우가 왼쪽 값을 얻고, 다른애가 왼쪽을 고른 것과 오른쪽을 고른 것 중 더 작은 값을 가지는 것
    int pickLeft = cards[left] + min(getMaxScore(cards, left+2, right), getMaxScore(cards, left+1, right-1));
    int pickRight = cards[right] + min(getMaxScore(cards, left+1, right-1), getMaxScore(cards, left, right-2));
    
    //두 경우 중 최대값을 DP 테이블에 저장
    return dp[left][right] = max(pickLeft, pickRight);
}

int main() {
    int T;
    cin >> T;
    
    while (T--){
        //각 카드 점수 입력
        int N;
        cin >> N;
        vector<int> cards(N);
        for (int i = 0; i<N; i++){
            cin >> cards[i];
        }
        
        //DP 테이블을 -1로 초기화
        memset(dp, -1, sizeof(dp));
        
        //0번부터 N-1번까지 카드가 있을 때 근우가 얻는 최대 점수 계산
        cout << getMaxScore(cards, 0, N-1) <<endl;
    }
    return 0;
}

 

 

프로님 설명 받아 적은 내용 ...

 

[DP테이블 정의하기]

dp[i][j]를 i번째 카드부터 j번째 카드까지 있을 때 근우가 얻을 수 있는 최대 점수로 정의한다.

 

-초기화

'i==j'인 경우, 즉 카드가 하나만 남아 있을 때, 근우는 남아있는 카드의 점수를 모두 가져갑니다. 따라서 dp[i][i]=카드의 점수[i]가 됩니다.

 

-점화식

근우가 왼쪽 카드i를 가져가면, 명우는 i+1부터 j까지 카드를 가져가게 됩니다.

근우가 오른쪽 카드 j를 가져가면, 명우는 i부터 j-1까지의 카드를 선택하게 됩니다.

 

왼쪽카드를 선택하면

a[i] + s(i,j) - d(i+1, j)

 

오른쪽카드

a[j] + s(i,j) - d(i, j+1)

 

이런 문제는 4선 DP로 쌓아올리거나, top-down or bottom-up으로 풀 수 있다.