배틀로얄
문제 해석
초기 체력 M을 가진 준석이 X명의 플레이어와 Y개의 체력 회복 아이템을 가진 맵에서 게임을 할 때, 모든 적과 아이템을 먹을 수 있는 경우를 출력하는 문제입니다.
적과 싸웠을 때 잃게 되는 체력은 M/2이하이고 체력회복 아이템을 최대 M/2만큼 회복할 수 있습니다.
체력 회복은 M을 초과하여 회복할 수 없습니다.
체력 0 이하이면 게임에서 집니다.
적들과 체력 아이템이 주어졌을 때 어떤 순서로 적을 죽이고 아이템을 먹어야하는지 출력합니다.
모든 적을 쓰러트리고 아이템을 모두 먹어야 합니다.
만약 게임에서 이길 방법이 없으면 첫번째 줄에 0을 출력합니다.
설계(15)
해당 문제는 그리디한 접근방법으로 풀이할 수 있습니다.
교전시 잃는 체력과 체력회복이 M/2이하이기 때문에 M/2보다 큰지 작은지로 교전할지 아이템을 먹을 지 판단하게 됩니다.
두개의 인덱스로 교전과 아이템 먹는 행위를 반복합니다.
모두 반복하고 남은 적과 아이템을 순차대로 진행했을 때 남은 체력이 0보다 작거나 같으면 0을 출력하도록 설정하면 됩니다.
구현(20)
코드(c++)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 100000
int person[MAXN], potion[MAXN];
vector<int> ans;
int X,Y,M,cur_M;
int idx1, idx2;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> X >> Y >> M;
cur_M = M;
for (int i = 0; i < X; i++) {
cin >> person[i];
}
for (int i = 0; i < Y; i++) {
cin >> potion[i];
}
int idx = 0;
while (idx1<X || idx2 < Y) {
if (idx1< X&& cur_M > M / 2) {
ans.push_back(-(idx1 + 1));
cur_M -= person[idx1++];
}
else if (idx2 < Y && cur_M <= M / 2) {
ans.push_back(idx2 + 1);
cur_M += potion[idx2++];
}
else break;
}
while (idx1 < X || idx2 < Y) {
if (idx1 < X) {
ans.push_back(-(idx1 + 1));
cur_M -= person[idx1++];
}
else if (idx2 < Y) {
ans.push_back(idx2 + 1);
cur_M += potion[idx2++];
}
}
if (cur_M <= 0) cout << 0 << "\n";
else {
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << "\n";
}
}
return 0;
}
코드(python)
import sys
input = sys.stdin.readline
X,Y,M = map(int,input().split())
person = [int(input()) for _ in range(X)]
potion = [int(input()) for _ in range(Y)]
ans = list()
idx1 = 0
idx2 = 0
cur_M = M
while idx1 < X or idx2 < Y:
if idx1 < X and cur_M > M//2:
ans.append(-(idx1+1))
cur_M -= person[idx1]
idx1+=1
elif idx2 < Y and cur_M <= M//2:
ans.append(idx2+1)
cur_M += potion[idx2]
idx2 += 1
else:
break
while idx1 < X or idx2 < Y:
if idx1<X:
ans.append(-(idx1+1))
cur_M -= person[idx1]
idx1 += 1
elif idx2 <Y:
ans.append(idx2+1)
cur_M += potion[idx2]
idx2 += 1
if cur_M <=0:
print(0)
else:
for i in ans:
print(i)
디버깅
c++ 구현할 때, 두번째 while문에서 idx2가 Y보다 작은 경우 person에 있는 값을 더해주는 실수를 하였습니다만 “맞았습니다”가 나왔습니다. 이것을 모르고 있다가 python으로 구현할 때 런타임 에러가 나오는 것을 보고 알아차리게 되었습니다.
틀린 코드인데도 통과된 이유는 고정된 배열을 미리 선언하여 사용하였기 때문에 오류가 없던것이 첫번째고, 두번째로 어떤 값이 나오던지 남은 체력에 더해지는 것이기 때문에 결과에 영향을 주지 않기 때문입니다.
이로써, 엣지케이스를 만들어보려고 했으나 위에서 언급했던 것처럼 값 자체가 무엇이냐에 따른 영향이 전혀 없었기 때문에 만들 수 없었습니다.
제출결과
40 ms (c++) 320 ms (pypy3)
마무리
그리디 접근방법으로 풀이 가능한 문제였습니다.