백준 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를 여러분이 계산해주면 좋겠다고 합니다.

문제풀이

사용한 알고리즘 : 이분탐색

(0) 생각

 x라는 체력으로 용사가 용을 쓰러트리기 가능한지는 O(N)으로 가능할 겁니다.

 N = 10^5 이니 최대 생명력을 알아보는데 log(N) 의 방법이 필요하다고 생각할 수 있고, 그 방법이 이분탐색입니다.

(1) 코드 50~60

 최대 생명력을 이분탐색으로 구현해줍니다.

 생명력의 범위를 문제에서 따로 주지 않았으므로, 적당히 큰 생명력을 최대로, 0을 최소로 설정 후 이분탐색 해주었습니다.

(2) 코드 20~38

 x 라는 생명력으로 용을 물리칠 수 있는지 판단하는 재귀함수입니다.

 각 단계의 용을 죽여야 다음 단계로 진행할 수 있음을 생각해줍니다.