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

문제

가슴에 의지를, 양손에 꽃을, 벛꽃 내리는 시대에 결투를!

이곳은 벚꽃 내리는 시대입니다. 이 세계에는 '여신'이라 불리는 초자연적인 존재들이 있습니다. 특별한 능력자, 미코토인 당신은 여신들의 힘을 깃들일 수 있습니다. 똑같이 여신들의 힘을 깃들인 다른 미코토들과의 결투, 벚꽃결투는 이곳의 대표적 문화입니다.

결투장에 들어간 미코토들은 방어력을 의미하는 오라와 생명력을 의미하는 라이프를 갖습니다. 라이프가 $0$ 이하가 되면 즉시 패배하게 됩니다.

그림 E.1: 여신 하츠미의 공격 '강산'(「 $3$ / $1$ 」)과 '오요기비 포화'(「 $2$ / $2$ 」).

이 결투에서의 모든 공격의 공격력은 두 가지 값 $X$ / $Y$ 를 가지며, $X$ 는 오라 공격력, $Y$ 는 라이프 공격력을 의미합니다. $X$ 와 $Y$ 는 각각 $0$ 이상의 정수 혹은 「 $-$ 」로 표현되며, $X$ 와 $Y$ 가 모두 「 $-$ 」인 경우는 없습니다. 공격을 받은 상대방은 오라에 $X$ 데미지를 받거나 라이프에 $Y$ 데미지를 받는 것 중 하나를 선택할 수 있습니다. 단, 상대방이 데미지를 선택할 때 몇 가지 추가 규칙이 적용됩니다.

공격 「 $X$ / $Y$ 」를 받았는데 현재 오라가 $X$ 보다 작을 경우, 무조건 라이프에 $Y$ 데미지를 받습니다.
공격 「 $X$ / $-$ 」를 받은 경우, 무조건 오라에 $X$ 데미지를 받습니다. 공격을 받았을 때 오라가 $0$ 미만이 될 경우, $0$ 으로 회복됩니다.
공격 「 $-$ / $Y$ 」를 받은 경우, 무조건 라이프에 $Y$ 데미지를 받습니다.

당신은 오라 $A$ 와 라이프 $L$ 만 남기고 간신히 생존해 있지만, 이번 차례만 넘기면 승리할 수 있는 전략을 갖고 있습니다. 하지만 유감스럽게도 지금은 상대 미코토의 차례입니다. 상대방은 당신의 오라와 라이프가 얼마 남지 않은 지금, 여신의 힘을 빌려 강력한 공격으로 이번 차례에 당신을 끝내려 할 것입니다. 그야말로 절체절명의 순간입니다!

당신은 상대방의 여신들이 어떤 공격 능력을 갖고 있고 상대방은 어떤 공격을 어떤 순서로 수행할지 간파하고 있습니다. 이런 상황에서, 상대방의 공격이 주는 데미지를 적절히 선택해 이번 턴을 무사히 넘기는 것이 가능하겠습니까? 가능하다면, 상대가 수행할 $N$ 개의 공격 각각의 데미지를 어떤 쪽으로 받아야 이번 턴을 무사히 넘길 수 있는지 구해 봅시다.

입력

첫 번째 줄에 상대방이 사용할 공격의 수 $N$ , 당신의 오라 $A$ , 당신의 라이프 $L$ 이 공백으로 구분되어 주어집니다.

이어지는 $N$ 개의 줄에는 상대방이 사용하려는 공격들에 대한 정보가 주어집니다. $N$ 개 줄 중 $i$ 번째 줄에는 $i$ 번째 공격의 공격력을 나타내는 두 값 $X_i$ 와 $Y_i$ 가 공백으로 구분되어 주어집니다. 이는 $i$ 번째 공격이 다음과 같음을 의미합니다.

$X_i,Y_i \ge 0$ 이라면, $i$ 번째 공격은 「 $X_i$ / $Y_i$ 」입니다.
$X_i = -1$ 이라면, $i$ 번째 공격은 「 $-$ / $Y_i$ 」입니다.
$Y_i = -1$ 이라면, $i$ 번째 공격은 「 $X_i$ / $-$ 」입니다.

출력

이번 턴에서 살아남을 수 있는 방법이 있는 경우 YES, 그렇지 않은 경우 NO를 출력합니다.

살아남을 방법이 있는 경우, 다음 줄에 A와 L만으로 구성된 길이 $N$ 의 문자열을 출력합니다. 이 문자열의 $i$ 번째 글자는 $i$ 번째 공격의 데미지를 받는 방법을 의미하며, A는 오라 데미지, L은 라이프 데미지로 받는 것을 의미합니다. 여러 가지 생존 방법이 존재한다면 그중 하나만 출력하도록 합니다.

출력은 대소문자를 구분하지 않습니다.

풀이

각 공격마다 오라로 받을지 라이프로 받을지 선택해야 하고, 끝까지 살아남을 수 있는 선택열도 복원해야 한다. 코드에서는 라이프 누적 피해를 상태로 두고, 그 상태에서 필요한 최소 오라 소모량을 DP로 계산한다.

solve(cnt, life)는 cnt번째 공격부터 처리할 때, 이미 라이프 피해를 life만큼 받은 상태에서 앞으로 필요한 최소 오라 피해량을 뜻한다. 오라로 받을 수 있으면 다음 상태의 최소 오라 소모량에 현재 오라 피해를 더하고, 라이프로 받을 수 있으면 라이프가 한계 L에 닿지 않는 경우에만 life + Y로 넘어간다.

모든 공격을 처리했을 때 필요한 최소 오라 피해가 현재 오라 $A$ 이하이면 생존 가능하다. 이후에는 DP 값이 유지되는 선택을 따라가며 A 또는 L을 출력해 실제 생존 방법을 역추적한다.

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n, a, l;
vector<pair<int, int>> atk;
long long dp[5001][5001]; // 최소 오라 소모량
 
long long solve(int cnt, int life) {	
	if (cnt == n) 
		return 0;
 
	long long &ret = dp[cnt][life];
	if (ret != -1) return ret;
 
	ret = 1e15;
 
	// 오라로 맞기
	if (atk[cnt].first != -1) {
		long long nxt = solve(cnt + 1, life);
 
		if (atk[cnt].second == -1 && nxt == 0) {
			ret = min(ret, 0LL); // 오라가 0 미만이 될 경우 0으로 회복
		} else {
			ret = min(ret, nxt + atk[cnt].first);
		}
	}
 
	// 라이프로 맞기
	if (atk[cnt].second != -1 && life + atk[cnt].second < l) 
		ret = min(ret, solve(cnt + 1, life + atk[cnt].second));
	
	return ret;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	cin >> n >> a >> l;
	atk.resize(n);
	memset(dp, -1, sizeof(dp));
 
	for (int i = 0; i < n; i++) 
		cin >> atk[i].first >> atk[i].second;
	
	if (solve(0, 0) <= a) {
		cout << "YES" << '\n';
		int life = 0;
 
		for (int i = 0; i < n; i++) {
			// 최선의 선택 역추적
			// 라이프 공격이 없으면 오라로 맞기
			if (atk[i].second == -1) {
				cout << 'A';
			}
			// 둘 다 있다면 오라로 맞는게 최선의 선택인지 확인
			else if (atk[i].first != -1 && 
				solve(i, life) == solve(i + 1, life) + atk[i].first) {
				cout << 'A';
			}
			// 아니면 라이프로 맞은 것 
			else {
				cout << 'L';
				life += atk[i].second;	
			}
		}
			
		cout << '\n';
	}
	else {
		cout << "NO" << '\n';
	}
 
	return 0;
}

복잡도

시간 복잡도: 공격 수를 $N$ , 라이프 한계를 $L$ 이라 하면 상태 수 기준 $O(NL)$ 이다.
공간 복잡도: DP 배열로 $O(NL)$ 을 사용한다.

마무리

이 문제는 공격을 맞는 순서를 바꾸는 문제가 아니라, 각 순간의 피해 선택을 DP로 남기는 문제다.

문제#

입력#

출력#

풀이#

코드#

복잡도#

마무리#

문제

입력

출력

풀이

코드

복잡도

마무리