백준 16434. 드래곤 앤 던전

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

16434번: 드래곤 앤 던전

 

이 문제는 보스방에서부터 첫방까지 거꾸로 거슬러 올라가면서 생각해야 하는 문제다.

용사가 마지막 보스를 쓰러트릴수 있는 최소의 maxHP를 구해야한다. 

maxHP가 최소가 되는 경우는 마지막 보스를 쓰러트렸을때 용사의 현재hp가 1 일때 일것이다.

 

마지막 방에서 부터 첫방까지 거슬러 올라간다. 

즉 각 방마다 구해야 하는 값은 해당 방에 진입하기 전 상태를 구해야 하는 것이다. 

 

몬스터 방일 경우 해당 몬스터방에 진입하기 전의 용사의 hp는 

현재 hp + (몬스터와 교전한 횟수 * 몬스터의 공격력) 이다.  (여기서 현재 hp란 해당 몬스터방을 클리어한 이후 hp일 것이다) 

 

포션 방일 경우 해당 포션방에 진입하기 전의 용사의 hp는 현재 hp - 포션 힐량 인데, 

조심해야 할점은 포션은 먹었을때 용사의 최대 hp까지만 회복되기 때문에 모든 힐량을 받지 않았을수도 있다는 점이다.

따라서 현재 hp - 포션 힐량 <= 0 이라면, 해당 포션방 진입 전 용사의 hp는 1이다.

 

마지막으로 답을 구할때도 포션의 존재 때문에 조심해야한다.

포션방에서 회복했을때 포션의 힐량을 모두 안받았을수도 있으므로, 답은 힐 받기전과 현재까지의 용사의 hp의 최댓값 중 큰 값이 된다. 

 

 

 

주의할 점들: 

- 포션은 먹었을때 용사의 최대 hp까지만 회복되기 때문에 모든 힐량을 받지 않았을수도 있다는 점

- 자료형 

- 몬스터와 교전시 몇턴 소요했는지 계산 (몬스터의 hp와 영웅의 공격력을 나눴을때 나머지가 있을때 없을때 차이) 

- 포션방에서 회복했을때 포션의 힐량을 모두 안받았을수도 있으므로, 답은 힐 받기전과 현재까지의 용사의 hp의 최댓값 중 큰값임.