BOJ 27163 벚꽃 내리는 시대에 결투를

문제 링크입니다.

살아남을 수 있는지 판단하기

살아남기 위해서는 마지막 공격을 받은 뒤 라이프가 1 이상이여야 합니다. 오라는 내 생존 여부를 직접적으로 결정하진 않지만, 남은 라이프가 같다면 오라가 많은 쪽이 공격을 흘릴 가능성이 더 높습니다.

여기서 다음과 같은 식을 세워 봅시다.

• $D[i][j]$ : $i$번째 공격을 받은 후 라이프가 $j$ 이상인 채로 남길 수 있는 최대 오라

이 DP는 공격이 들어옴에 따라 배낭 문제처럼 DP 테이블을 채워 주면 쉽게 구할 수 있습니다. Bottom-Up으로 구하는 쪽이 편할 겁니다.

도달 불가능한 상태의 표현을 위해 기본적으로 테이블은 -1과 같이 절대 나오지 않을 값으로 초기화해 줍니다. 이때, 만약 N번째 공격을 받은 뒤 살아남을 수 있다면, $D[N][1]$은 0 이상이 됩니다.

살아남는 방법 찾기

이 DP를 역추적해서 안 아프게 맞는 방법을 찾아봅시다.

추가로 다음과 같은 값을 관리합니다.

• $V[i][j]$ : $D[i][j]$의 값을 최대화하기 위해 i번째 공격을 맞는 방법 (0이면 라이프, 1이면 오라)

DP를 돌릴 때 V의 값도 함께 갱신해 주면, 역추적은 $D[N][1]$부터 $V$의 값에 따라 라이프 또는 오라를 회복시키면서 돌아가는 컨셉으로 해결할 수 있습니다.

최종 시간 복잡도 $\mathcal{O}(NL)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;

int d[5432][5432];
bool v[5432][5432];
int n, a, l;
int ld[5432];

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	memset(d, -1, sizeof(d));
	cin >> n >> a >> l;
	for(int i = 1; i <= l; i++) d[0][i] = a;
	
	for(int i = 1; i <= n; i++){
		int adam, ldam; cin >> adam >> ldam;
		ld[i] = ldam;
		
		if(adam == -1){
			for(int j = l; j > ldam; j--){
				if(d[i-1][j] != -1){
					d[i][j-ldam] = d[i-1][j];
					v[i][j-ldam] = 1;
				}
			}
		}
		
		else if(ldam == -1){
			for(int j = l; j >= 1; j--){
				if(d[i-1][j] != -1){
					d[i][j] = max(0, d[i-1][j]-adam);
					v[i][j] = 0;
				}
			}
		}
		
		else{
			for(int j = 1; j <= l; j++){
				if(d[i-1][j] >= adam){
					d[i][j] = d[i-1][j]-adam;
					v[i][j] = 0;
				}
				if(j > ldam){
					if(d[i][j-ldam] < d[i-1][j]){
						d[i][j-ldam] = d[i-1][j];
						v[i][j-ldam] = 1;
					}
				}
			}
		}
	}
	if(d[n][1] != -1){
		cout << "YES\n";
		int life = 1;
		stack<char> st;
		for(int i = n; i >= 1; i--){
			if(v[i][life]){
				st.push('L');
				life += ld[i];
			}
			else{
				st.push('A');
			}
		}
		while(!st.empty()){
			cout << st.top();
			st.pop();
		}
	}
	else cout << "NO";
}