개요

백준 16434번: 드래곤 앤 던전

• 입력
  첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다.

  i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 ≤ ai, hi ≤ 1,000,000) 가 주어집니다.

  ti가 1인 경우 공격력이 ai이고 생명력이 hi인 몬스터가 있음을 나타내고, ti가 2인 경우 용사의 공격력 HATK를 ai만큼 증가시켜주고 용사의 현재 생명력 HCurHP를 hi만큼 회복시켜주는 포션이 있음을 나타냅니다.

• 출력
  용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 출력합니다.

접근 방식

• 입력값이 많은 관계로 구조체로 입력값을 받아온다.

• 이분탐색으로 접근을 해서 주인공의 maxHp가 각각의 mid값일 때
  조건을 만족한다면, 해당 mid값으로 high값을 갱신한다.
  만족을 못할 시, 해당 mid값으로 low값을 갱신한다.
  low값과 high값의 차이가 1날 때까지 반복하여 조건을 만족하는 high값의 최솟값을 찾는다.

• 실수했던 부분은

  1. 회복포션을 사용했을 때 체력이 maxHp보다 커지면 체력을 maxHp로 조정 하는 부분을 빼먹었다.
  2. 몬스터의 체력과 주인공 공격력을 따로 변수로 빼서 관리해야하는데 그대로 접근해서 썼다가 초기화를 까먹어서 답이 안 나왔다.
  3. 이분탐색 안의 과정에서 서로 때리는 과정을 계산하지 않고

  while (monHp > 0 && curHp > 0)
  				{
  					//몬스터를 공격 
  					monHp -= curAtk;
  					//몬스터 피 0이하면 종료
  					if (monHp<= 0) {
  						break;
  					}
  					//플레이어를 공격
  					curHp -= v[i].secondParam;
  					//플레이어는 끝까지 살아있어야 N번 방을 깨므로 한번이라도 죽으면 false
  					if (curHp <= 0) return false;
  
  				}*/

  이런식으로 반복문으로 구현했더니 최악의 상황인 주인공 공격력 1 체력 100만 이상,
  적 공격력 1 체력 100만일 때 저 부분에서 이미 100만^2의 연산을 해서 시간초과가 뜬다.

  따라서 플레이어가 몬스터를 몇 대 때려야 죽는지와 몬스터가 플레이어를 몇대 때려야 죽는지를
  미리 알아내서 계산을 해 반복문과정을 없앴다.

  				//몬스터 피
  				long long monHp = v[i].thirdParam;
  				//플레이어가 몬스터 죽을때 까지 때려야할 수
  				long long playerStrike = ((monHp % curAtk==0) ? monHp/curAtk : (monHp/curAtk +1));
  				//몬스터가 플레이어 죽을때까지 때려야할 때린 수
  				long long monsterStrike = ((curHp % v[i].secondParam == 0) ? curHp / v[i].secondParam :( curHp / v[i].secondParam + 1));
  				//플레이어가 때려야하는 수가 몬스터가 때려야하는 수보다 더 많으면 플레이어가 진다.
  				if (playerStrike > monsterStrike) return false;
  				//플레이어가 때려야하는 수가 같거나 더 적다면 플레이어가 선공이므로 이긴다.
  				//몹은 플레이어가 때린거보다 한대 덜때려야한다.
  				curHp -= v[i].secondParam * (playerStrike - 1);
  

코드

#include<iostream>
#include<vector>

using namespace std;
int roomAmount=0, initAtk = 0;

struct roomInfo
{
	int typeRoom;
	int secondParam;
	int thirdParam;
}; 

vector<roomInfo> v;
void input() {
	int temp1=0, temp2=0, temp3=0;
	cin >> roomAmount >> initAtk;
	for (int i = 0; i < roomAmount; i++) {
		cin >> temp1 >> temp2 >> temp3;
		roomInfo rInfo = {temp1, temp2,temp3};
		v.push_back(rInfo);
	}
}

/// <summary>
/// mid값일 때 용을 쓰러뜨린다면 true 리턴, 못쓰러뜨리면 false return
/// </summary>
/// <param name="mid"></param>
/// <returns></returns>
bool checkMxHp(long long mid) {

	long long curHp = mid,curAtk=initAtk;
	for (int i = 0; i < roomAmount; i++) {
		//몬스터 공격일 때
		if (v[i].typeRoom == 1) {
			//몬스터 피
			long long monHp = v[i].thirdParam;
			//플레이어가 몬스터 죽을때 까지 때려야할 수
			long long playerStrike = ((monHp % curAtk==0) ? monHp/curAtk : (monHp/curAtk +1));
			//몬스터가 플레이어 죽을때까지 때려야할 때린 수
			long long monsterStrike = ((curHp % v[i].secondParam == 0) ? curHp / v[i].secondParam :( curHp / v[i].secondParam + 1));
			//플레이어가 때려야하는 수가 몬스터가 때려야하는 수보다 더 많으면 플레이어가 진다.
			if (playerStrike > monsterStrike) return false;
			//플레이어가 때려야하는 수가 같거나 더 적다면 플레이어가 선공이므로 이긴다.
			//몹은 플레이어가 때린거보다 한대 덜때려야한다.
			curHp -= v[i].secondParam * (playerStrike - 1);

		}

		//회복 방이라면
		else if (v[i].typeRoom == 2) {
			//회복 수치가 maxhp값 보다 크다면
			if (curHp+v[i].thirdParam >= mid) 
				curHp = mid;
			else {
				curHp += v[i].thirdParam;
			}
			curAtk += v[i].secondParam;
		}
	}
	return true;
}


void solution() {
	//high값은 나올수 있는 최대값인 방 최대갯수(123,456) 와 
    //플레이어 공격력 1,체력 100만이상, 적 공격력 1, 체력 100만일때의 연산값인 100만^2을 곱한 값에 1더해서 설정하였다.
	long long low = 0, high = 123'456'000'000'000'001,mid=0;
	while (low + 1 < high) {
		mid = (low + high) / 2;
		((checkMxHp(mid))? high:low)=mid;
	}
	cout << high;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	input();
	solution();
}

문풀후생

시간초과되는 반복문 고치는 부분은 제외 하고서라도
입력값으로 받아온 데이터를 사용했다가 초기화 안 하는 실수랑, 문제 조건인 회복량부분 확인 제대로 안한 부분은 심각한 것 같다.
더 신중해지면 좋을 것 같다.