18866번 - 젊은 날의 생이여
문제의 지문에 행복도와 피로도는 실수라는 조건이 적혀있기 때문에 누락된 값(0)의 경우는 무시하고 K날에서의 행복도, 피로도의 최대/최소값을 갱신해주면 된다는 점을 알고 있습니다.
하지만 처음 문제를 풀이할 땐, 이와 같은 사실을 모르고 누락된 값(0)을 모두 유효한 값으로 변경한 뒤 Prefix, Suffix Min/Max 값을 구해주어 풀이하였는데요, 제 풀이의 누락된 값을 채우는 과정에서 반례가 존재한다는것을 발견했습니다.
예를 들어, 행복도의 누락된 값을 이전의 값에서 0.1씩 줄여 채우는 식으로 코드를 작성했음에도 정답 처리가 됩니다.
1310 10 20 30 40 50 60 70 80 90 100 110 129 13[answer]12[output]10
즉, 10과 9 사이에 매우 많은 실수가 존재하기 때문에 0이 몇개가 들어와도 문제가 없어야 하지만, 고작 11개가 들어와도 문제가 발생합니다.
만약 테스트케이스를 추가하게 된다면 N의 최대값인 1,000,000이 입력으로 들어오는 경우를 만들어 추가해야 할 것 같습니다.
채점번호76243735
댓글을 작성하려면 로그인해야 합니다.
jeong5728 2년 전
문제의 지문에 행복도와 피로도는 실수라는 조건이 적혀있기 때문에 누락된 값(0)의 경우는 무시하고 K날에서의 행복도, 피로도의 최대/최소값을 갱신해주면 된다는 점을 알고 있습니다.
하지만 처음 문제를 풀이할 땐, 이와 같은 사실을 모르고 누락된 값(0)을 모두 유효한 값으로 변경한 뒤 Prefix, Suffix Min/Max 값을 구해주어 풀이하였는데요, 제 풀이의 누락된 값을 채우는 과정에서 반례가 존재한다는것을 발견했습니다.
예를 들어, 행복도의 누락된 값을 이전의 값에서 0.1씩 줄여 채우는 식으로 코드를 작성했음에도 정답 처리가 됩니다.
13
10 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
9 13
[answer]
12
[output]
10
즉, 10과 9 사이에 매우 많은 실수가 존재하기 때문에 0이 몇개가 들어와도 문제가 없어야 하지만, 고작 11개가 들어와도 문제가 발생합니다.
만약 테스트케이스를 추가하게 된다면 N의 최대값인 1,000,000이 입력으로 들어오는 경우를 만들어 추가해야 할 것 같습니다.
채점번호
76243735