nabongsun   1년 전

안녕하세요, 제 나름대로 코딩을 해서 완벽하다고 생각했었는데, 계속 제출만 하면 틀렸어요.. 여러 게시판 뒤져가며 찾은 반례들도 다 맞았는데요.. 

그런데 입력데이터를 한번 정렬해 주니깐, 바로 정답이 되더라구요?? 

16번줄에 sort(seq.begin(), seq.end()); 이게 왜 빠지면 안되는지 설명해주실분 있으실까요?? 

감사합니다.

niji_k   1년 전

후술할 설명에서 "왼쪽"은 배열의 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가 성립하므로, 조건문에서 해당 조건을 빼도 정답 코드가 됩니다.

shs0911   1년 전

데이터를 정렬해야 dp로 LIS를 구할 수 있기 때문입니다. 

예를 들어서 {7, 3}, {2, 2} 순서로 전깃줄이 입력되었다고 합시다. 그러면 2 < 7 && 2 < 3을 만족하므로 dp값을 증가시켜야 합니다.

이 때, 정렬을 해야만 {2, 2}의 전깃줄이 {7, 3}의 전깃줄보다 앞으로 위치하게 되고(배열 상에서), 원하는 dp값을 구할 수 있게됩니다.

정렬을 하지 않는다면 7 < 2 && 3 < 2이 참이 아니므로 dp값이 증가하지 않습니다.

nabongsun   1년 전

헉 자세한 답변들 감사합니다.


저도 같은 전깃줄을 순서만 바꾸어 넣어보니, sort가 없을경우 오답이 나오는것을 발견하고 이유를 생각해보니, 제가 쓴 코드는 정렬된 데이터에만 적절한 해답을 내주는 코드였던거 같습니다. 


주어진 예제에서는 10 10을 기준으로 왼쪽의 데이터들이 대부분 오름차순 정렬이 되어있고,  오른쪽의 데이터들이 내림차순 정렬이 되어있어, 작동을 했던거 같습니다.


감사합니다.

nabongsun   1년 전

추가로 제가 확인 해보았던 반례입니다. 

input:

4

1 4

3 2

2 1

4 3

output:

1

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