[문제]
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으로 풀 수 있다.
'코딩테스트 준비 > C++' 카테고리의 다른 글
| [백준 c++] 7579 앱 (0) | 2024.08.09 |
|---|---|
| [C++] 다익스트라 알고리즘 (0) | 2024.08.06 |
| [백준 C++] 1000번 : A+B | C++ 숫자 입력 받기, C++ Python 시간 비교 (0) | 2024.08.06 |
| [백준 C++] 2557번 : Hello World | C++ 3가지 입출력 정리 (0) | 2024.08.06 |