인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

모모추르값버는중님의 프로필 이미지

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

5-H (13144) 질문

작성

·

385

0

선생님 안녕하세요 ~ 문제를 풀다 질문이 생겨 글을 남깁니다 !

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 - 인덱스 를 답으로 처리해주는 부분을 추가했는데요

제출시 오답으로 나오는 이유를 모르겠습니다. ! 어느 부분의 논리가 틀린걸까요 ...?!

 

답변 2

0

큰돌님의 프로필 이미지
큰돌
지식공유자

굉장히. 아이디어가 좋은 코드입니다.

일단 피벗을 걸어넣고 그 부분을 포함하는 "중복되지 않은 수열"을 더해서 답을 만들어가는 것. 좋습니다.

but, 반례입니다.

8

1 1 1 1 1 2 2 2

 

답은 9가 나와야 하는데 모모님의 코드는 11을 반환합니다.

모모추르값버는중님의 프로필 이미지

선생님, 어느부분이 이상한지 이해했습니다 ~!!! 감사합니다 !!!!!!

0

큰돌님의 프로필 이미지
큰돌
지식공유자

안녕하세요. ㅎㅎ 코드 다 봤는데요.

나머지 부분은 다 이해가 가는데 다음 코드 조금만 더 설명 가능할까요?

제 생각에는 이 코드는 마지막 부분을 처리하는 것 같은데요. 예를 들어 갱신되는 구간을 다 처리한 후 1 2 3 4 5 처럼 마지막의 경우 등차수열의 합으로 처리하는 부분인 것 같은데 맞나요?

for(int i=1; i<=100000; i++) if(cnt[i]!=0) ans += (n+1-cnt[i]);
모모추르값버는중님의 프로필 이미지

넵 맞습니다 ! 의도는 그렇게 해서 짰는데, 오답으로 나오는 이유를 모르겠습니다 !!