백준 16434 (드래곤 앤 던전) - 이분탐색

문제

---

용사는 공주를 구하기 위해 무시무시한 용이 있는 던전으로 향하기로 하였습니다. 우선 용사는 용사 자신과 던전을 분석하였습니다.

용사에게는 세 종류의 능력치가 있습니다. 

• HMaxHP : 용사의 최대 생명력입니다. 이 값은 1이상이어야 하며 던전에 들어간 이후로 변하지 않습니다.
• HCurHP : 현재 용사의 생명력입니다. 던전에 들어가기 전 이 값은 용사의 최대 생명력 HMaxHP와 같습니다. 이 값은 HMaxHP보다 커질 수 없습니다.
• HATK : 용사의 공격력입니다.

던전은 총 N개의 방으로 이루어져 있고 i번째 방을 통해서만 i+1번째 방으로 이동 할 수 있습니다. 방에는 포션이 있거나 몬스터가 있는데 몬스터가 있을 경우 몬스터를 쓰러트려야지 다음방으로 이동 할 수 있습니다. N번째 방에는 공주와 용이 있고, 용을 무찌르면 공주를 구할 수 있습니다.

몬스터가 있는 방에 올 경우 다음과 같이 전투가 진행됩니다.

1. 용사의 공격력 HATK만큼 몬스터의 생명력을 깎습니다.
2. 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
3. 몬스터의 공격력만큼 용사의 생명력 HCurHP를 깎습니다.
4. 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
5. 다시 1부터 진행합니다.

포션이 있는 방에 올 경우 포션을 마셔서 현재 용사의 생명력 HCurHP가 일정량 회복되고 공격력 HATK도 일정량만큼 증가됩니다. 회복된 생명력이 최대 생명력 HMaxHP보다 큰 경우 용사의 현재 생명력 HCurHP가 최대 생명력 HMaxHP와 같아집니다.

용사는 던전으로 향하기 전에 만반의 준비를 하고 있습니다. 용사는 수련을 하면 최대 생명력 HMaxHP를 늘릴 수 있는데 얼마나 수련해야 할지 고민입니다.

용사는 N번 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 여러분이 계산해주면 좋겠다고 합니다.

 

 

 

 

 

풀이

---

문제에서 두가지 주의사항이 있다.

1. 용사의 HP가 0이 되는 순간 게임은 종료된다.
2. 용사의 포션을 아무리 먹어도 최대 HP보다 많아지지 않는다.

이 두가지 주의 사항은 잘 생각하며 문제를 풀어야한다.

 

문제는 완전탐색을 해도 답은 나오지만 시간복잡도를 줄이기 위해서 이분탐색을 하였다.

최소 HP는 1이므로, left = 1 

최대 HP는 그때그때 다르므로 계산으로 해줬다.

if(rooms[i][0] == 1) {
	right += rooms[i][1] *( rooms[i][2] / atk_now);
}
else {
	atk_now += rooms[i][1];
}

right 값은 몬스터를 통해 받는 피해의 최대량을 구했다.

 

이렇게 양끝값을 구해서 이분탐색을 한다.

long left = 1;
while(left <= right) {
	long mid = (left + right) / 2;
	long hp = mid;
	atk_now = atk;
	//게임시작
	for(int i = 0 ; i < n ; i++) {
		if(rooms[i][0] == 1) {
			long times = rooms[i][2] / atk_now;
			// 용사의 공격이 먼저이므로 용의 공격한번은 뺴준다.
			if(rooms[i][2] % atk_now == 0) {
				times--;
			}
			
			hp -= rooms[i][1] * times;
		}
		else {
			atk_now += rooms[i][1];
			// 최대 hp보다 포션이 크다면 최대 hp 만큼만 회복한다.
			if(mid - hp < rooms[i][2]) {
				hp = mid;
			}
			else {
				hp += rooms[i][2];
			}
		}
		//게임종료 게임을 나간다.(용사가 죽었다.)
		if(hp <= 0)
			break;
	}
	
	if(hp <= 0) {
		left = mid + 1;
	}
	else {
		right = mid - 1;
	}
}

게임을 마무리 지었을 때의 hp 값을 기준으로 left 값과 right 값을 바꿔주면 된다.

 

 

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static int n;
	static long atk;
	static long[][] rooms;
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		n = Integer.parseInt(st.nextToken());
		atk = Long.parseLong(st.nextToken());
		
		rooms = new long[n][3];
		long right = 0;
		long atk_now = atk;
		for(int i = 0 ; i < n ; i++) {
			st = new StringTokenizer(bufferedReader.readLine());
			rooms[i][0] = Long.parseLong(st.nextToken());
			rooms[i][1] = Long.parseLong(st.nextToken());
			rooms[i][2] = Long.parseLong(st.nextToken());
			
			if(rooms[i][0] == 1) {
				right += rooms[i][1] *( rooms[i][2] / atk_now);
			}
			else {
				atk_now += rooms[i][1];
			}
		}
		
		
		long left = 1;
		while(left <= right) {
			long mid = (left + right) / 2;
			long hp = mid;
			atk_now = atk;
			//게임시작
			for(int i = 0 ; i < n ; i++) {
				if(rooms[i][0] == 1) {
					long times = rooms[i][2] / atk_now;
					// 용사의 공격이 먼저이므로 용의 공격한번은 뺴준다.
					if(rooms[i][2] % atk_now == 0) {
						times--;
					}
					
					hp -= rooms[i][1] * times;
				}
				else {
					atk_now += rooms[i][1];
					// 최대 hp보다 포션이 크다면 최대 hp 만큼만 회복한다.
					if(mid - hp < rooms[i][2]) {
						hp = mid;
					}
					else {
						hp += rooms[i][2];
					}
				}
				//게임종료 게임을 나간다.(용사가 죽었다.)
				if(hp <= 0)
					break;
			}
			
			if(hp <= 0) {
				left = mid + 1;
			}
			else {
				right = mid - 1;
			}
		}
		System.out.println(left);
	}
}