후술할 설명에서 "왼쪽"은 배열의 0번 인덱스를 향하는 방향, "오른쪽"은 배열의 마지막 인덱스를 향하는 방향으로 정의하겠습니다.
19~25번 라인은 해당 부분에서는 먼저 전깃줄 하나를 기준으로 잡고, 그 전깃줄보다 왼쪽에 있는 전깃줄 중에
기준이 되는 전깃줄과 겹치지 않는 전깃줄의 수를 세어 저장하려는 의도로 보입니다.
27~33번 라인은 반대로 기준이 되는 전깃줄의 오른쪽에 있는 전깃줄을 세어 저장하려는 의도로 보입니다.
위에서, 19~25번 라인은 아무 일도 하지 않습니다. (seq가 정렬됐으니, i>j이면 seq[i]>seq[j]는 항상 참 >> seq[i]<seq[j]는 항상 거짓)
27~33번 라인이 실제 계산을 수행한다고 보시면 되겠습니다.
해당 코드가 제대로 작동하려면, 임의의 seq[x]보다 왼쪽에 연결되어 있는 모든 전깃줄의 정보는 seq[x]의 왼쪽에 위치해야 합니다.
만약에 seq[x]보다 오른쪽 인덱스에 seq[x]보다 왼쪽으로 연결된 전깃줄의 정보가 있는 경우, 모든 전깃줄을 검사하지 않기 때문에 오답을 낼 가능성이 있기 때문입니다.
즉, 입력 데이터인 seq가 seq[x].first 기준으로 정렬되어 있어야만 27~33번 라인이 제대로 작동합니다.
주어지는 입력값은 seq 순서대로 전깃줄의 데이터가 주어지지 않기 때문에, 먼저 정렬을 해야만 해당 부분이 제대로 작동합니다.
또한, seq가 정렬되면 i<j를 만족하는 모든 (i,j) 쌍에 대해 seq[i].first<seq[j].first가 성립하므로, 조건문에서 해당 조건을 빼도 정답 코드가 됩니다.
nabongsun 1년 전
안녕하세요, 제 나름대로 코딩을 해서 완벽하다고 생각했었는데, 계속 제출만 하면 틀렸어요.. 여러 게시판 뒤져가며 찾은 반례들도 다 맞았는데요..
그런데 입력데이터를 한번 정렬해 주니깐, 바로 정답이 되더라구요??
16번줄에 sort(seq.begin(), seq.end()); 이게 왜 빠지면 안되는지 설명해주실분 있으실까요??
감사합니다.