[C++/백준] 16434 드래곤 앤 던전

https://www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

 

 

[문제 요약]

MaxHP : 최대 생명력, 1이상 필수

curHP : 현재 용사 생명력 (최대 MaxHP)

ATK : 용사 공격력 

 

1) 방을 한 칸씩 이동하고, 방에는 포션이나 몬스터가 있다.

2) 몬스터의 피가 0이 될 때까지 공격을 주고 받는다. (용사 선공)

  2-1) 몬스터 공격력 만큼 용사 생명력을 차감

  2-2) 용사 피가 0이 되면 안된다. 

3) 포션을 먹으면 curHP가 충전되고, Max_HP를 넘을 순 없다. 

 

[아이디어 구현 과정]

일단, 처음 문제를 보고 생각난 풀이 방법은 1) 완전 탐색 2) 이진 탐색 이었다. 

1번 부터 생각해보면, N은 12,4000에 중간 중간 로직을 고려해주는 것도 힘들어서 안된다는 걸 알 수 있었고, 

2번으로 생각했다. 

 

이진 탐색을 사용할 경우에 end값을 어떻게 처리하냐? 가 있었는데

1) 모든 데미지의 총합(포션을 제외)을 MAX로 사용한다

2) 누적합으로 잘 구해본다

 

두 가지 방법이 생각이 났다. 

1번을 고려했을 때, 1,000,000 * 12,3000 -> 10^11 정도가 되는데 long long에 담기나? 하는 생각이 들었고

<참고로 알아보니 충분히 담깁니다ㅎㅎ,,>

2번으로 생각하던 중에 이진탐색을 사용하지 않고도 가능할 거라는 생각이 들었다. 

 

그래서 이진탐색은 버리고, 약간의 그리디 + 누적합을 사용해서 풀었다. 

 

 

[풀이]

 

로직은 되게 간단한데, 누적합으로 용사에게 쌓이는 데미지를 계속 저장하고 

가장 크게 누적되는 데미지를 구한다. 

그리고 +1 ( 최대 HP 최소 ) 를 저장한다 ㅇㅇ..

 

1. 몬스터를 만날 때( t == 1)

1) 용사가 몬스터를 처치하는데 필요한 공격수를 구해준다.

    => 나누기, 반올림으로 구함.

2) 용사가 몬스터에게 받는 데미지를 저장

    => 용사 선공이기 때문에 1)에서 구한 횟수 x 몬스터의 공격력

3) 누적합 : 이전 누적 데미지 + 이번에 받는 데미지

4) 이제껏 받은 누적 데미지 중 최대 누적 데미지를 구한다.

 

2. 포션일 때 (t == 2)

1) 누적합 : 이 전까지의 데미지 누적 - 회복 량

2) 공격력 += 포션 공격력

3) 누적합은 0 이하가 될 수 없다. 

 

 

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>

using namespace std;

int N;
long long ATK;
long long Max_HP;
vector<long long> DMG(130000);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> ATK;
	DMG[0] = 0;
	for (int i = 1; i <= N; i++) {
		int t, a, h;
		cin >> t >> a >> h;
		// t == 1 : 몬스터
		long long dmg = 0;
		if (t % 2) {
			long long num = ceil(double(h) / double(ATK));
			dmg = (num - 1) * a;
			DMG[i] = DMG[i - 1] + dmg;
			Max_HP = max(DMG[i], Max_HP);
		}
		else {
			dmg = DMG[i - 1] - h;
			ATK += a;
			DMG[i] = dmg >= 0 ? dmg : 0;
		}
	}
	cout << Max_HP + 1;
}

 

---

풀이 시간은 50분 정도였고, 

굳이 누적합을 매번 정해주지 않아도 구할 수 있지만, 이진 탐색을 염두에 두고 시작해서 배열에 담게 됐다 ㅎㅎ..

-> 생각을 못한게 조금 아쉬움.