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
또한 용사의 공격력이 1이고 몬스터의 공격력이 최대(1000000)이며 이러한 방이 123456개 있을 경우 long long으로 출력이 가능한지 확인하였고, 모든 방이 회복 포션이거나 몬스터가 약해서 한 방컷일 경우에는 최대 생명력이 1이 되도록 만들었습니다.
하지만 그럼에도 계속 틀렸습니다가 나옵니다. 위의 방식이 잘못된 거 같은데 어떤 부분이 잘못 됐는지와 반례가 궁금합니다. 손으로 계산한 값과 비교하는데 매번 같은 걸 보니 문제를 잘못 이해한게 아닌가 싶기도 하고... 아무리 읽어봐도 제가 놓치고 있는 부분이 뭔지 도저히 모르겠네요..
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이 되도록 만들었습니다.
하지만 그럼에도 계속 틀렸습니다가 나옵니다.
위의 방식이 잘못된 거 같은데 어떤 부분이 잘못 됐는지와 반례가 궁금합니다.
손으로 계산한 값과 비교하는데 매번 같은 걸 보니 문제를 잘못 이해한게 아닌가 싶기도 하고...
아무리 읽어봐도 제가 놓치고 있는 부분이 뭔지 도저히 모르겠네요..
읽어주셔서 감사합니다.