jeongbeen   4년 전

arr 배열에 공격을 받았을 경우 -를 붙여 음의 값으로, 회복 포션을 마셨을 경우 양의 값으로 넣어주었습니다.
그 이후 정렬을 통해, 체력이 가장 많이 깎였을 때의 값(arr[0])과 이를 제외하고 끝까지 더한 값(sum)을 구했습니다.
만약 sum이 양수라면 의미가 없기 때문에 |arr[0]-1|을 출력하고, sum이 음수면 |arr[0]+sum-1|을 출력했습니다.

위와 같이 생각한 이유는 다음과 같습니다.

3 3
1 1 20  >>>> -6
2 3 10  >>>> 10
1 3 100  >>> -48

arr[0] = -48, sum = 4;
|arr[0]-1| = 49

만약 최대 생명력이 49이라 가정하고 직접 풀어보면,
첫번째 방 : 49 - 6 = 43
두번째 방 : 회복 포션 +10이므로 따라서 49까지 회복
세번째 방 : 49 - 48 =1

따라서 49가 최소 최대생명력이 맞으므로,
sum>=0이면 | arr[0]-1 |이 정답이라 생각했고

3 3
1 1 20  >>>> -6
2 3 1  >>>> 1
1 3 100  >>>>-48

arr[0] = -48, sum = -5;
|arr[0]+sum-1| = 54

만약 최대 생명력이 54이라 가정하면
첫 번째 방: 54 - 6 = 48
두 번째 방: 회복 포션 +1, 따라서 49까지 회복
세 번째 방: 49 - 48 = 1

따라서 54가 최소의 최대생명력이 맞으므로,
sum<0이면 | arr[0]+sum-1 |이 정답이 맞다고 생각했습니다.

또한 용사의 공격력이 1이고 몬스터의 공격력이 최대(1000000)이며 이러한 방이 123456개 있을 경우 long long으로 출력이 가능한지 확인하였고, 
모든 방이 회복 포션이거나 몬스터가 약해서 한 방컷일 경우에는 최대 생명력이 1이 되도록 만들었습니다.

하지만 그럼에도 계속 틀렸습니다가 나옵니다.
위의 방식이 잘못된 거 같은데 어떤 부분이 잘못 됐는지와 반례가 궁금합니다.
손으로 계산한 값과 비교하는데 매번 같은 걸 보니 문제를 잘못 이해한게 아닌가 싶기도 하고...
아무리 읽어봐도 제가 놓치고 있는 부분이 뭔지 도저히 모르겠네요..

읽어주셔서 감사합니다.

seico75   4년 전

두번째 케이스에서 체력이 49면 어떻게 되나요?

jeongbeen   4년 전

답 없는 가독성과 오타 때문에 글을 조금 수정했습니다. 번거롭게 해드려 죄송합니다ㅠㅠ
두번째 케이스에서 몬스터의 체력이 49일 때면
3 3
1 1 49
2 3 1
1 3 100
64가 출력 됩니다..!

seico75   4년 전

제가 작성하신 코드에서 arr 를 잘못 봤네요.

반례입니다. 답은 61이 나와야할 것 같습니다.

8 3 
1 1 31
1 1 31
1 1 31
1 1 31
1 1 31
1 1 31
2 3 70
1 3 100

jeongbeen   4년 전

와 정말 감사합니다!
| arr[0] | < sum (체력포션 제외) 인 경우도 있군요!
덕분에 많이 배워갑니다. 좋은 하루 보내세요. 감사합니다!


댓글을 작성하려면 로그인해야 합니다.