BOJ 2336 굉장한 학생

N명의 학생이 세 번의 시험을 치룬 결과가 주어지는데, 세 번의 시험에서 한 학생이 다른 한 학생보다 세 번 모두 성적이 좋으면 더 "대단한" 것인데, 어떤 학생보다 "대단한" 학생이 없다면 그 학생은 "굉장한" 학생이다. 이 때, 굉장한 학생의 수를 구하는 문제이다.

즉, 자신보다 세 번 다 성적이 좋은 학생이 없는 학생의 수를 구하는 문제이다. (0번, 1번, 2번 성적이 좋은 학생들의 수)

문제 분류가 '세그먼트 트리'로 되어있는데, 쉽게 떠오르지 않는다. 처음부터 세그먼트 트리로 생각하려 해서 그런가? 한 번 그냥 푼다면 어떻게 풀 것인지 생각해 봐야겠다.
갑자기 떠오른 생각이, 굉장한 학생의 수를 바로 구하는 것보다, 굉장하지 않은 학생의 수를 구해서 빼는 게 나을 것 같다.
굉장하지 않은 학생의 수는 자신보다 세 번 모두 성적이 좋은 학생이 있는 학생의 수를 구하면 된다.

집중도 안되고 딴생각만 들고... 결국 풀이를 봤는데도 잘 이해가 안된다. 어렵다.
정신 차리고 차근차근히 풀이를 정리해 보자. 독서백편 의자현. 이해될 때까지...
일단 굉장한 학생의 수를 구해야 한다. 굉장한 학생은 자신보다 세 번 모두 성적이 좋은 학생이 없어야 한다. 문제에서는 등수 순으로 주어진다.

2 5 3 8 10 7 1 6 9 4
1 2 3 4 5 6 7 8 9 10
3 8 7 10 5 4 1 2 6 9

블로그도 보고, 백준님의 코드도 보고 하면서 생각도 하고 예제를 가지고 직접 써보다가 겨우 깨달았다. 정말 헷갈린다.
일단 각 학생별로 1번 학생이 세 시험에서 각각 몇등을 했는지, 2번 학생이 세 시험에서 가각 몇 등을 했는지,... n번 학생이 세 시험에서 각각 몇 등을 했는지를 기록한다.
그리고 세 개의 시험 중 하나의 시험의 등수를 기준으로 정렬한다. 여기서 많이 헷갈렸는데, 정렬해버리면 몇 번 학생이 몇 등했는지는 알 수 없다. 하지만 알 필요없다. 우리는 굉장한 학생의 수만 구하면 된다. 정렬했기 때문에 몇 번 학생인지는 몰라도 첫번째 시험에서 1등한 사람이 두번째 시험과 세번째 시험에서 몇 등을 했는지를 알 수 있다.
즉, 누군지는 몰라도 한 사람이 각 시험에서 몇 등을 했는지에 대한 정보가 하나의 시험을 기준으로 정렬되어 있다. 2번째 시험을 기준으로 정렬했다고 하고 예를 들어보겠다.
왼쪽부터 한 사람씩(한 열씩) 보면 두번째 시험에서 1등을 한 사람은 첫번째, 세번째 시험에서 각각 2등, 3등을 했다는 사실을 알 수 있다. 일단 사람1은 두번째 시험에서 1등이므로 첫번째, 세번째 시험에서 자기보다 잘한 학생이 있어도 굉장한 학생이다. 이제 사람2를 보자. 이제 사람2부터는 (정렬을 했으므로) 항상 두번째 시험에서 자기보다 잘한 사람이 1명 이상 있다. 굉장한 학생은 자신보다 세 시험 성적이 모두 좋은 사람이 없어야 하는데, 사람2부터는 두번째 시험에서 자신보다 잘 본 사람이 있다. 그리고 정렬했기 때문에 두번째 시험에서 자신보다 잘 본 사람들은 앞에 존재하고, 그 사람들이 첫번째와 세번째 시험에서도 자신보다 성적이 좋다면 그 사람은 굉장한 학생이 될 수 없지만, 첫번째 시험과 세번째 시험 둘 중 하나에서라도 자신이 성적이 제일 좋다면(자신보다 성적이 좋은 사람이 없다면) 그 학생은 굉장한 학생이 될 것이다.

많이 헷갈린다. 지금 두번째 시험을 기준으로 정렬하고 앞에서부터 보기 때문에 항상 자신의 앞사람들은 자신보다 두번째 시험은 잘 본 사람들이고, 이제 그 사람들의 첫번째 시험과 세번째 시험의 성적이 자신보다 좋아야 자신은 굉장한 학생이 될 수 없는 것이다. 두번째 시험을 자신보다 못 본 사람들은 첫번째 시험과 세번째 시험 성적이 아무리 좋아도 볼 필요가 없다. 세 시험에서 모두 자신보다 성적이 좋은 사람이 한 사람이라도 있는지 봐야하고 만약 있다면 자신은 굉장한 학생이 아니게 된다.
그래서 두번째 시험을 기준으로 정렬하고 나서는 두번째 시험에서 자신보다 앞에 있는 사람에 대해서 그 사람들의 첫번째, 세번째 시험 성적을 보면되고, 여기서 첫번째 시험 성적 중 가장 좋은 성적과 자신의 첫번째 성적을 비교하고 , 세번째 시험 성적 중 가장 좋은 성적과 자신의 세번째 성적을 비교해서 첫번째, 세번째 모두 자신의 성적보다 좋으면 그 사람은 굉장한 학생이 될 수 없고, 그 중 하나라도 자신의 성적보다 안 좋다면 그 사람은 굉장한 학생이 된다! 왜냐하면 각 성적 중 가장 좋은 성적을 가져왔기 때문에 그 가장 좋은 성적이 자신의 성적보다 좋지 않다면 자신이 그 사람들 모두보다 성적이 더 좋은 것임을 바로 알 수 있기 때문이다. 즉 그 중에 자신보다 세 시험 모두 성적이 좋은 사람이 한 사람도 없다는 것을 바로 알 수 있기 때문이다.
그래서 구간의 최소값을 빠르게 구할 수 있어야 하는데, 풀이를 좀 더 보니 내 방법에서 좀 더 나아가 segment tree를 이용해야 하는 것 같다. 하지만 일단 n제한이 50만이니까 O(N)만에 누적 최소값을 계산해두고(첫번째 부터 n번째 까지의 최소값이 필요하므로) 사용하면 될 것 같다. 일단 내가 생각한대로 풀어봐야겠다.

근데 내 방법으로 계속 틀리길래... 계속 고민하고 풀이를 찾아 읽어봤지만 도무지 알 수가 없던 차에
5
1 2 3 4 5
5 4 3 2 1
1 2 3 5 4
라는 예제를 가지고 백준님의 코드와 내 코드의 실행 결과를 비교해 봤더니 달랐다. 감사합니다... 바로 찾다니 그리고 저 예제로 생각해보고 내 풀이의 문제점을 알게되었다.

내가 대충 이해한 것은 맞다. 하지만 내 풀이처럼 첫번째 따로, 세번째 따로 찾게되면 한 학생의 첫번째, 세번째 점수가 아닌, 예를 들면 학생1의 첫번째 점수, 학생2의 세번째 점수와 비교하게 될 수 있다. 왜 이걸 전혀 생각 못했지... 정말 요즘 더 실력이 떨어진 것 같다... 노력하자.

그래서 이제 다시 생각해 봐야한다.... 음 이제 내가 참고했던 여러 풀이가 이해가 된다.
왜 굳이 세그먼트 트리를 쓰는지조차 이해가 잘 안됐는데, 아... 다시 정리해 보겠다.

일단 위에서 설명했던 것처럼 두번째 시험을 기준으로 성적이 좋은 순으로(오름차순) 정렬하고 첫번째와 세번째를 보는데 위에서 잘못한 것 처럼 따로 보면 안되고 한 사람 한 사람 단위로 봐야한다!! 일단 두번째 시험을 기준으로 정렬하고 앞에서부터 보기 시작하면 자신의 앞에 있는 사람은 두번째 시험의 경우 항상 자신보다 성적이 좋다. 그리고 자신보다 뒤에 있는 사람은 두번째 시험 성적이 항상 자신보다 안 좋으므로 첫번째, 세번째 성적이 아무리 좋아도 자신보다 "대단할" 수 없다. 그래서 일단 자신보다 앞에 있는 사람들이 첫번째, 세번째 성적이 모두 자신보다 좋은 "대단한" 사람이 될 수 있는 후보들이다. 이 중에서 자신(현재 학생)보다 대단한 사람이 없다면 현재 학생이 굉장한 사람이 되는 것이다.

두번째를 정렬해서 봐야할 곳을 첫번째와 세번째 두 곳으로 줄였지만, 여전히 첫번째와 세번째 모두 현재 학생보다 성적이 좋은 것을 찾는 것이 쉽지 않다. 바로 이 때 세그먼트 트리를 써줄 것인데, 이번에는 첫번째 성적을 기준으로 정렬을 하는 효과를 내보자.
바로 첫번째 시험의 성적(등수)을 해당하는 세번째 시험 등수값의 인덱스로 지정한다. 그리고 그것으로 세그먼트 트리를 만들어서 range minimum query를 할 수 있게 하고 현재 학생의 첫번째 시험 성적보다 좋은 성적에 해당하는 구간의 최소값(즉, 그 구간에 해당하는 세번째 시험의 성적중 가장 좋은 성적)을 구해서 현재 학생의 세번째 시험 성적과 비교하고 그 성적이 현재 학생의 세번째 성적보다 좋으면 현재 학생보다 "대단한" 학생이 존재하는 것이고, 만약 아니라면 "대단한" 학생이 없는 것이므로 현재 학생은 "굉장한" 학생이 된다.

엄청난 풀이다...

그리고 처음에는 segement tree를 매우 큰 값으로 초기화 해두고, 학생을 한 명씩 볼 때마다, 즉, 두번째 시험 기준으로 정렬된 순서에 따라 첫번째 성적에 해당하는 부분을 업데이트를 시켜줘야 한다. 왜냐하면 현재 학생의 첫번째 시험 성적보다 좋은 성적에 해당하는 구간이여도 이미 정렬했던 두번째 시험 성적을 기준으로 볼 때, 두번째 성적이 더 좋은 성적이 아닐 수 있기 때문에 그럴 경우에는 세그먼트 트리에 실제 첫번째 성적과, 세번째 성적에 대한 정보대신 매우 큰 값이 들어가 있어서 더 "대단한"학생이 아닌 것으로 제대로 판단하게 된다.

어렵다. 내가 너무 나태해져서 머리가 잘 안 돌아가는 것 같기도 하다. 맥그리거의 말 처럼 멈추지 말고 쉬지도 말고 끊임없이 노력하자.

음 근데, 구현하면서도 문제가 좀 있었다.
일단 init을 INF로 해주는 것에서 leaf node만 INF로 해주었다던가... 또한 update를 구현할 때, update하려는 index가 구간의 범위 밖이면 그 구간의 rangeMin값을 반환해줘야 하는데, 마치 query처럼 INF를 반환해준 것... 정말 실력 부족이다...

그리고 일반 정수가 아닌 struct는 bool cmp(struct, struct)를 쓸 때, 그냥 쓰면 복사하는데 비용이 커지므로 const struct& 식으로 참조자를 사용해서 구현하자.

위의 것도 다 고쳤는데...근데 도대체 뭐에서 틀렸을까...
정말 랜덤데이터를 생성해서 여러번 시도해 봤는데도.. 틀린 경우를 찾을 수가 없어서 고민하다가 문득.. tree를 INF로 초기화해야 하는데, init함수를 그냥 for문으로 고치고 0번 노드부터 n*4-1번노드까지 무작정 INF로 초기화하고 제출했다. 그러니까 AC를 받았다.

헉... 분명 이 것은 아까 테스트를 해봤던 것이다. 혹시 제대로 안 들어가나 해서 rangeMin값이 잘 초기화 되었는지 출력해서 확인까지 해봤었는데... 뭐지...그래서 코드를 다시 봤는데..

헉...init함수 마지막줄에 rangeMin=min(leftMin, rightMin)만 해주고 return을 안하고 있다...근데 아까는 어떻게 INF값으로 초기화 된 것이지..??? 그냥 내 local환경에서만 된 것인가.. 설마 그래서 아무리 틀린케이스를 찾으려해도 못 찾았던 것인가... 아.. 의문이 하나 둘씩 풀린다. 진짜 이 문제만큼 (백준님의 정답 코드가 있음에도 불구하고, 풀이를 이해했음에도 불구하고) 틀린 이유를 찾기 힘든 적은 처음인 것 같다.

결국 init함수에서 내 실수로 인해... 제대로 초기화가 안됐고.. 계속 틀렸던 것이다.
다시 짜봐야 겠다.

이 문제를 풀게 되면서, 그리고 다시 짜보면서 init이나 update함수부분을 좀 더 잘 이해하게 된 것 같다. 아직 완벽히 이해했다고는 생각치 않지만...
그리고 bool cmp(struct, struct)에서 &(참조자)를 써야 더 빠를 것 같았는데 제출해보니 찍히는 시간상으로는 차이가 없어보인다. 그냥 int형이라면 포인터나 int형이나 크기가 비슷하니까 상관없겠지만 struct의 경우 int형이 지금 코드에서 3개라.. 12byte짜리를 복사할텐데.. 음 BOJ 가 64비트 시스템으로 바뀌고 나서 포인터가 8byte 가 되서 큰 차이가 없는 것인가... 여튼 웬만하면 const struct& 형식으로 쓰는 게 좋을 것 같다.


<참고>
http://blog.naver.com/kks227/220791986409
http://cloge.tistory.com/7
백준님 강의 자료, 코드