글 읽기 - 16434번 - 드래곤 앤 던전 틀렸다는데 반례를 모르겠습니다.

wl9322 3년 전 0

몇 일째 도전중인데 도저히 반례를 모르겠습니다.

예제는 물론 다통과하였습니다.

일단 들어온 데미지보다 많이 회복되는 경우 혹은 마지막 방보다 전 방에서의 데미지가 더 크지만 포션방에서 다회복 될경우는

모두 실험해봤는데 잘되었습니다. 이거 말고 어떤 반례가 있을지 몰라서 너무 어려워 풀지 못하고 있습니다. 반례를 가르쳐주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

long long zero = 0;

void sol(long long N, long long Ha, queue<long long> dungeon) {
	long long t, a, h;
	long long cur_d = 0, max_h = 0;
	//O(n)풀이
	for (int i = 0; i < N; ++i) {
		//해당 방의 정보 추출
		t = dungeon.front();//방 구분(몬스터, 포션)
		dungeon.pop();
		a = dungeon.front();//몬스터, 포션의 공격력 수치
		dungeon.pop();
		h = dungeon.front();//몬스터, 포션의 체력 수치
		dungeon.pop();

		if (t == 1) {
			cur_d += a * (ceil((double)h/Ha) - 1);//현재방에서 누적된 데미지 계산
			if (cur_d > max_h) max_h = cur_d;//현재방까지 와서 누적된 데미지가 이전에 누적된 데미지보다 클 시 그만큼의 체력이 필요하므로 답으로 바꿈
		}

		else {
			Ha += a;//공격력 상승
			cur_d = max(cur_d - h, zero);//최대체력을 넘어 회복이 안되므로 누적된 데미지 보다 체력이 많이 회복 될경우 현재 데미지가 -가 되므로 0과 현재 데미지 중에 큰값 선택
		}
	}
	cout << max_h + 1;//최대체력 계산시 딱 맞는 데미지만 들어오므로 그거보다 1이 높아야 용사가 죽지 않으므로 1을 더하여 출력
}

int main() {
	long long N, Ha, input;
	queue<long long> dungeon;

	cin >> N >> Ha;

	for (int i = 0; i < N * 3; ++i) {
		cin >> input;
		dungeon.push(input);
	}

	sol(N, Ha, dungeon);

	return 0;

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

16434번 - 드래곤 앤 던전 틀렸다는데 반례를 모르겠습니다.

wl9322 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말