dinojslee   1년 전

왜 틀렸는지 모르겠습니다

다른 컴파일러에서는 예제대로 입출력이 작동하는데 반례가 혹시 있을까요?

skuru   1년 전

반례입니다.

입력

0
0
0
0
1
0
0
1
0
0

출력

3

정답

2

moner_ari   1년 전

우선 반례 드립니다. 이 반례들은 testcase.ac 이라는 사이트에서 찾아볼 수 있습니다.

입력:

4
2
2
5
2
3
3
3
2
3

오답 출력:

6

정답 출력:

4

입력:

6
6
7
7
7
8
8
8
8
8

오답 출력:

6

정답 출력:

3

입력:

9
9
9
9
9
10
10
10
10
10

오답 출력:

6

정답 출력:

2

--------

코드를 한번 확인해보니, 16번 줄의 for문에서 j < count 부분이 잘못된 것으로 보입니다. 질문자 분의 코드에서 count는 서로 다른 나머지의 개수를 의도한 것으로 보이는데, 그 count까지만 j를 돌려서 판단하신다면 실제로는 이미 나온 나머지라서 개수(count)를 세지 말아야 하는데도 개수를 세는 문제가 생깁니다.

예를 들어, 3번째 반례의 경우에는 처음 9에서는 count = 1이고, 2~5번째 9에서는 이미 9가 존재하기 때문에 count를 세지 않습니다. 1번째 10에서는 9가 아닌 다른 나머지가 나왔기 때문에 count를 세줍니다. 하지만 2번째 10에서는 {9, 9, 9, 9, 9, 10, 10, 10, 10, 10}에서 바로 앞에 10이 나왔기 때문에 count를 세지 말아야 하지만, 실제로는 {9, 9, 9, 9, 9, 10}까지만 판별해서 10 != 9라고 판단해서 count를 세게 됩니다. 이런 잘못된 판단이 2~5번째 10에서 계속 일어나서, 6이라는 오답이 나오는 것입니다.

dinojslee   1년 전

이해했습니다! rest 배열에 나머지가 순차적으로 들어가는 것이 아니라 항상 i번째 위치에 저장되다 보니 문제가 생긴 거군요! 정말 감사합니다!!

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