[CodeJam][2017] Play the Dragon - Round1A ProblemC

문제 : https://code.google.com/codejam/contest/5304486/dashboard#s=p2&a=2

---

- IMPOSSIBLE

내가 한 번에 knight를 죽일 수 없고 (첫 번째 턴에서 끝낼 수 없음)

knight에게 2번 이하 맞으면 죽는 경우 (첫 번째 턴에서 지거나, 나는 계속 힐해야 함)

-> 

단, 2번 맞았을때 죽는 경우(& 첫번째 턴에 나이트 못죽임)는 첫 번째 턴에 버프나 디버프를 건다.

버프를 걸었을 때 한 번 공격하면 나이트가 죽는 경우 이길 수 있다.

디버프를 걸었을 때 2번 맞아도 안죽는 경우 내가 이길 수 있다.

- knight 턴에서는 무조건 나를 때린다. (정해져 있는 조건)

디버프를 쓰려면 무조건 초반에 몰아서 써야 이득이다.

- 회복 횟수, 나이트 공격력, 디버프의 상관관계

회복 횟수는 나이트의 공격력과 관계있다.

회복 횟수 = 올림 (체력 / 나이트 공격력)

나이트 공격력은 디버프 횟수와 관계있다.

나이트 공격력 = 나이트 공격력 - 디버프 횟수

즉, 회복 횟수 = 올림 (체력 / (나이트 공격력 - 디버프 횟수))

그러므로 디버프 횟수는 0부터 1씩 증가하면서 비교하지 않아도 되고

회복 횟수(체력 / (나이트 공격력 - 디버프 횟수))가 바뀔 만큼의 디버프 횟수만 케이스로 쳐서 비교하면 된다.

- 기타

버프, 디버프는 누적된다. -> 무조건 공격이전에 버프를 적용하면 좋다.

따라서 디버프, 버프, 공격 순으로 나온다.

치유는 무조건 피를 Hd 만큼 채우므로 죽기 전에 한 번만 해주면 된다.

- 결론

따져봐야 하는 것은 버프와 디버프 횟수다.

공격 횟수는 버프 횟수와 나이트 체력에 의존되고

회복 횟수는 디버프 횟수와 내 체력에 의존되기 때문이다. 

---

정리해본 조건들.

위 조건으로 SMALL은 어떻게든 풀 수 있을 것 같은데 LARGE는 가능할지 모르겠다. 조건이 10^9라 흠흠..

판단해야하는 조합을 더 줄여야 되나 싶다.

SMALL도 특정 버프, 디버프 일 때 턴 횟수 계산하는 코드 아직 안짜봤지만 좀 까다로울 것 같아서 막막.

---

+ 19/02/10 SMALL

위에서 언급한 조건들을 모두 사용하진 않았다.

막상 짜보니 회복 횟수를 구하는 것이 까다로워 시뮬레이션으로 SMALL은 풀었다.

SMALL 범위는 각 조건이 최대 100이여서 가능하다. 그래서 버프, 디버프도 이중 for문을 이용해서 완탐했다.

(Large인 경우 조건이 10^9 이기 때문에 2중 for문을 돌리면 TLE)

불가능 한 경우도 시뮬레이션을 사용하여 힐이 필요한 경우 힐을 한 번 하고 힐을 한 바로직후에는 힐이 아닌 이외의 행동을 한다. (공격, 버프, 디버프 중 1)

만약 힐이 아닌 다른 행동한 턴에서 나이트에게 공격받아 죽는다면 IMPOSSIBLE한 경우다.

공격받아 죽지 않기 위해 힐을 한다면 힐을 연속으로 두 번 한 경우이므로 지지는 않을 수 있지만 이길수는 없다. (공격을 해야 나이트의 피를 깎아 이길 수 있기 때문이다.)

주의해야 할 점은 힐을 해야 하는 조건이었다.

버프를 걸고 있는 경우 나는 나이트를 공격하지 않으므로 나이트의 피를 고려하지 않아도 된다. 

나이트가 나를 공격할 때의 데미지는 일정하므로 힐을 해야 하는 조건은 현재 남은 피 - 나이트 공격력 <= 0 이다.

디버프를 걸고 있는 경우 버프와 마찬가지로 나는 나이트를 공격하지 않으므로 나이트의 피를 고려하지 않아도된다.

하지만 디버프 중이므로 나이트의 공격력은 달라진다. 따라서, 힐을 해야 하는 조건에서 나이트 공격력은 디버프를 걸었을 때를 가정해서 판단해야 한다. 즉, 힐 필요 조건은 현재 남은 피 - (나이트 공격력 - 디버프(D)) <= 0 이다.

공격을 하고 있는 경우에는 버프나 디버프가 없으므로 서로의 공격력은 일정하다.

따라서 기본 조건은 현재 남은 피 - 나이트 공격력 > 0 이다.

하지만 순서를 생각해본다면 나는 선공격을 할 수 있다.

따라서 이번 턴에서 내가 나이트를 한 대 때려서 이길 수 있다면 힐이 필요한 상황이여도 굳이 힐을 하지 않아도 된다.

즉, 최종 조건은 (현재 남은 피 - 나이트 공격력 <= 0) && !(나이트 남은 피 - 내 공격력 <= 0) 이다.

---

+ 19/02/10

소스코드(SMALL) : https://gist.github.com/fpdjsns/d99f5b1133b142fb8d505c367fcee702