5-H (13144) 질문

Question

선생님 안녕하세요 ~ 문제를 풀다 질문이 생겨 글을 남깁니다 ! https://www.acmicpc.net/problem/13144 문제 링크 http://boj.kr/37f120d6ba16481cb0425be0b64fc8c6 코드 링크   해당 문제에서, 저도 기존에 없던 수가 들어오면 배열 cnt에 인덱스를 저장하고, 기존에 있던 수가 들어오면 답 += (현재 인덱스 - 이전 인덱스) 를 하고 인덱스를 갱신했습니다.   그리고 마지막에 아직 계산되지 않은 수들을 위해서, (갱신되지 않아 답 처리가 안된 수들) for(int i=1; i<=100000; i++) if(cnt[i]!=0) ans += (n+1-cnt[i]); 한번 이상 카운트 된 수들에 대해서 n+1 - 인덱스 를 답으로 처리해주는 부분을 추가했는데요 제출시 오답으로 나오는 이유를 모르겠습니다. ! 어느 부분의 논리가 틀린걸까요 ...?!

큰돌 · Answer

굉장히. 아이디어가 좋은 코드입니다. 일단 피벗을 걸어넣고 그 부분을 포함하는 "중복되지 않은 수열"을 더해서 답을 만들어가는 것. 좋습니다. but, 반례입니다. 8 1 1 1 1 1 2 2 2   답은 9가 나와야 하는데 모모님의 코드는 11을 반환합니다.

큰돌 · Answer

안녕하세요. ㅎㅎ 코드 다 봤는데요. 나머지 부분은 다 이해가 가는데 다음 코드 조금만 더 설명 가능할까요? 제 생각에는 이 코드는 마지막 부분을 처리하는 것 같은데요. 예를 들어 갱신되는 구간을 다 처리한 후 1 2 3 4 5 처럼 마지막의 경우 등차수열의 합으로 처리하는 부분인 것 같은데 맞나요? for(int i=1; i<=100000; i++) if(cnt[i]!=0) ans += (n+1-cnt[i]);