kks227   10달 전

중등부 문제라는데 도저히 중등부 문제라는 것을 믿을 수 없어하면서 제 머리로 몇 시간에 걸쳐 솔루션을 이해하고 짜본 결과 20% 가량에서 마주치는 비교적 작은 테스트 케이스에서 오답을 뱉는다고 합니다.

일단 51~55번 줄에서 점들을 X좌표 기준으로 정렬한 후 X좌표마다 증가하는 순으로 새로운 번호를 매겼고

56~58번 줄에서 점들을 Y좌표 기준으로 재정렬하고(이때 튜플의 x, y 원소 순서가 바뀝니다)

60~69번 줄에서 가능한 모든 Y1, Y2의 쌍에 대해 등장 가능한 모든 maxsum을 얻어보고 그 중 최댓값을 찾아서 result에 넣는 중입니다. 이때 같은 Y좌표 점들은 반드시 한번에 처리하려 했습니다.

어디가 잘못된 걸까요? 실수를 몇 개나 다잡아봤지만 여전히 틀려서 결국 의욕이 떨어졌습니다. 앞쪽의 큼직해보이는 케이스 2개는 통과했는데... 뭔가 사소한 예외처리가 잘못된 것 같습니다.

koosaga   10달 전

만약에 빈 집합에 -1이 하나가 달랑 들어가 있다면 정의상 maxsum은 0인가요 -1인가요? 저도 저거때문에 처음 할 때 엄청 해멨던 기억이.. ㅠㅠ


추가로 저 문제는 대회때 만점자가 없었습니다. 

kks227   10달 전

엄밀히는 -1이 나와야 하겠지만, 문제에서 w가 양수인 자원이 최소 하나 있다고 해서 result가 일단 0보다 클 것이라 생각해서 그런 부분을 신경쓰지 않았는데, 다시 한 번 생각해 보니까 문제가 꼭 안 되리라는 보장도 없네요. 한번 생각해 봐야겠습니다.

ㅋㅋㅋㅋ 문제가 너무 어렵네요... 제가 정올 출신은 아니지만 아무리 봐도 중등부 수준이 아닌데...

kks227   10달 전

4

1 1 4
1 2 6
2 1 7
2 2 -1000

이런 최소 케이스는 실험해 봐서 11이 잘 나왔었는데, 하루 동안 잠만 자다가 일어나서 방금 전에

4
2 2 4
1 2 6
2 1 7
1 1 -1000

이 케이스를 넣어보니까 갑자기 17을 뱉어내서 디버깅했더니 맞았습니다.

x좌표를 새로 매기는 부분에서, 이미 이전 x좌표가 바뀌어 버렸는데 그거랑 같은지 비교를 하고 있어서 문제가 생겼네요.

이게 대체 어떻게 두 개의 큰 케이스를 통과한건지는 의문이지만... 그래도 해피엔딩 이군요

도와주신 koosaga님께 다시 한번 감사의 말씀 드립니다.

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