오랜만에 돌아온 백준
https://www.acmicpc.net/problem/27163
문제 분석
벚꽃 내리는 시대에 결투를 이라는 보드게임에서 아이디어를 얻어 백준 문제로 만든 것입니다.
- 기본적으로 플레이어는 방어력을 의미하는
오라와 생명력을 의미하는라이프를 지닙니다.- 만약 라이프가 0이되면 게임에서 패배합니다.
결투를 하기에 플레이어에게 공격이 들어옵니다.
공격은 X/Y 라는 형식으로 표현됩니다. X, Y는 숫자 또는 -(none)입니다.
- X/Y : X의 데미지를 오라로 받거나, Y의 데미지를 라이프로 받습니다. 만약 오라가 X보다 작아 방어할 수 없다면 무조건 Y의 데미지를 라이프로 받습니다.
- X/- : X의 데미지를 오라로 받습니다. Y가 오라보다 큰 경우 오라는 0이 됩니다.
- Y/- : Y의 데미지를 오라로 받습니다.
플레이어는 이번턴만 버티면 게임에서 승리합니다.
상대방이 사용할 공격 리스트가 주어질 때 플레이어가 어떤 방식으로 데미지를 받아야 생존할 수 있을까요?
접근
일단 기본적으로 당연히 임의의 n번째 공격이 들어올때, 라이프, 오라가 많은게 이득입니다.
그런데 둘중 어느게 많아야 이득인지는 알 수 없기에 두 값을 일단 관리해야합니다.
그렇다면 관리해야하는 값은 3개입니다.
- 몇번째 공격인가
- 라이프가 몇인가
- 오라가 몇인가
이전 값에 다음 값이 영향을 받고 그리디가 성립하지 않기에 무난하게 dp를 생각해 볼법합니다.
범위를 봐볼까요?
공격은 최대 5000개 주어집니다.
그리고 플레이어의 오라는 최대 10억, 라이프는 최대 5000입니다.
일단 오라는 절대로 dp의 한 축으로 잡을 수 없습니다.
dp[10억] 한줄만 잡아도 4GB로 메모리초과가 발생합니다.
그렇다면 오라는 다른 방식으로 관리해야합니다.
생각해보면 dp로 추구하는 것은 비용의 최대화, 최소화 등이 있습니다.
그리고 저희가 풀어야할 문제에는 비용이란게 없고, 생존가능성만 계산하면 됩니다.
이 값은 임의의 공격, 임의의 라이프, 임의의 오라에 대해 무조건 true or false입니다.
그리고 저희는 위에서 오라는 최대화 되는게 이득이다 말했습니다.
그렇기에 오라를 dp의 축이 아닌 값으로 이동 시킬 수 있습니다.
임의의 공격, 임의의 라이프에 대해가능한 오라가 최대가 되면 생존가능한가?
이렇게 하면 dp 배열이 5000 x 5000으로 나와 모든 조건을 테스트해볼 수 있습니다.
구현
dp[0][L] 로 시작합니다.
for문을 통해 dp[0][0] ~ dp[0][L]을 돕니다.
만약 dp[0][i]에 값이 존재하면 dp[1][i-Y]에 dp[0][i]를 적어넣거나(라이프로 받음), dp[1][i]에 dp[0][i]-X를 적어넣습니다(오라로 받음).
(특수해 [ex. X > A] 도 처리합니다.)
이때 오라가 최대인 것이 이득이기에 오라가 가장 큰 것을 저장하고 만약 값이 갱신된다면 라이프로 받은지, 오라로 받는지도 적어둡니다.
이것을 모든 공격에 대해 반복하고
최종적으로 dp[N][1~L] (0 제외) 를 돌며 값이 존재하는지 찾고 값이 있다면 그것으로부터 저장해뒀던 공격데이터를 통해 역추적을 하며 답을 출력합니다.
만약 값이 없다면 생존할 수 없기에 NO를 출력합니다.
코드
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <stdlib.h>
#include <stack>
#include <cmath>
#include <cstring>
#include <deque>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#define MOD 1000000007
#define MODULAR(x,y) (((x)%MOD)+((y)%MOD))%MOD
#define MODULARF(x,y) (((x)%MOD)*((y)%MOD))%MOD
#define MODULARM(x,y) (((x)%MOD)-((y)%MOD))%MOD
#define ll long long
#define F first
#define S second
using namespace std;
int dp[5001][5001];
bool check[5001][5001];
vector<int>v;
int main(){
int n,a,l;
cin>>n>>a>>l;
int aa,la;
for (int j = 0; j <= l; j++) {
dp[0][j] = -1;
}
dp[0][l] = a;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= l; j++) {
dp[i][j] = -1;
}
cin >> aa >> la;
v.push_back(la);
for (int j = 1; j <= l; j++) {
if (dp[i - 1][j] != -1) {
if (aa == -1) {
dp[i][max(0, j - la)] = max(dp[i][max(0, j - la)], dp[i - 1][j]);
check[i][max(0, j - la)] = true;
}
else if (la == -1) {
dp[i][j] = max(0, dp[i - 1][j] - aa);
check[i][j] = false;
}
else {
if (dp[i - 1][j] < aa) {
if (dp[i][max(0, j - la)] < dp[i - 1][j]) {
dp[i][max(0,j-la)] = dp[i-1][j];
check[i][max(0, j - la)] = true;
}
}
else {
if (dp[i][max(0, j - la)] < dp[i - 1][j]) {
dp[i][max(0, j - la)] = dp[i - 1][j];
check[i][max(0, j - la)] = true;
}
if (dp[i][j] < max(0,dp[i - 1][j]-aa)) {
dp[i][j] = max(0, dp[i - 1][j] - aa);
check[i][j] = false;
}
}
}
}
}
}
string ans="";
int base = n;
for (int i = 1; i <= l;i++) {
if (dp[n][i] != -1) {
base=i;
for (int j = v.size() - 1; j >= 0; j--) {
if (check[j + 1][base]) {
ans ='L' + ans;
base+=v[j];
}
else {
ans = 'A' + ans;
}
}
break;
}
}
if (ans == "") {
cout<<"NO";
}else{
cout<<"YES\n";
cout<<ans;
}
}좀 예전에 짠거라 깔끔하진 않네요.
