16434

문제풀이

용사가 던전에서 용을 쓰러트리고 공주를 구하기 위한 최소 maxHP를 결정하는 문제

입력

• n, atk : 던전의 방의 갯수, 용사의 초기 공격력
• i 번째 방의 정보 - t, a, h
  • t 가 1이면 공격력 a, 생명력이 h인 몬스터
  • t 가 2이면 공격력을 a만큼 증가시키고 생명력을 h만큼 회복

로직

1. 입력을 받는다.
2. 최소 체력과 최대 체력을 선언한다.
3. 던전을 클리어 할 수 있는 최소 체력값을 선언한다.
4. 이분 탐색을 수행한다.
   1. mid값이 용사의 최대 체력일 때 던전을 클리어하는지 체크한다.
   2. 클리어하면 반환할 값을 갱신하고 용사의 최대 체력을 낮춰서 클리어 가능한지 확인한다.
   3. 클리어 못하면 최대체력을 늘려서 던전을 클리어 할 수 있는지 체크한다.
5. 던전을 클리어 할 수 있는 최소 체력값을 반환한다.

맞왜틀

• 최대 입력값이 용사의 공격력은 1이고 던전 방의 정보가 1 1000000 1000000 으로 123456줄이 들어 올 수 있다. C++코드로 실행시 123455876544000001가 출력되며 자바스크립트로 코드로 실행시 이분탐색으로 Onlogn의 시간복잡도로 풀면 시간초과가 발생하고 On의 시간복잡도로 각 던전 방의 데미지를 계산해서 최대 hp를 구하면 틀렸습니다 결과가 출력된다. 자바스크립트의 Number는 부동소수점 타입으로 큰 값에서는 정확한 계산이 되지 않아서 BigInt를 사용해서 계산해야 된다.
• 최대값이 1e15까지는 69%에서 답이 틀리고 1 e16부터는 69%에서 시간초과로 실패 하며 최대 입려값을 받으려면 1e18 크기정도 지정되어야 한다.

리팩토링