용사가 던전에서 용을 쓰러트리고 공주를 구하기 위한 최소 maxHP를 결정하는 문제
- n, atk : 던전의 방의 갯수, 용사의 초기 공격력
- i 번째 방의 정보 - t, a, h
- t 가 1이면 공격력 a, 생명력이 h인 몬스터
- t 가 2이면 공격력을 a만큼 증가시키고 생명력을 h만큼 회복
- 입력을 받는다.
- 최소 체력과 최대 체력을 선언한다.
- 던전을 클리어 할 수 있는 최소 체력값을 선언한다.
- 이분 탐색을 수행한다.
- mid값이 용사의 최대 체력일 때 던전을 클리어하는지 체크한다.
- 클리어하면 반환할 값을 갱신하고 용사의 최대 체력을 낮춰서 클리어 가능한지 확인한다.
- 클리어 못하면 최대체력을 늘려서 던전을 클리어 할 수 있는지 체크한다.
- 던전을 클리어 할 수 있는 최소 체력값을 반환한다.
- 최대 입력값이 용사의 공격력은 1이고 던전 방의 정보가 1 1000000 1000000 으로 123456줄이 들어 올 수 있다. C++코드로 실행시 123455876544000001가 출력되며 자바스크립트로 코드로 실행시 이분탐색으로 Onlogn의 시간복잡도로 풀면 시간초과가 발생하고 On의 시간복잡도로 각 던전 방의 데미지를 계산해서 최대 hp를 구하면 틀렸습니다 결과가 출력된다. 자바스크립트의 Number는 부동소수점 타입으로 큰 값에서는 정확한 계산이 되지 않아서 BigInt를 사용해서 계산해야 된다.
- 최대값이 1e15까지는 69%에서 답이 틀리고 1 e16부터는 69%에서 시간초과로 실패 하며 최대 입려값을 받으려면 1e18 크기정도 지정되어야 한다.