swc0317   1년 전

이전에 스위핑 북서풍 문제를 지금과 같은 방식으로 풀었습니다.

대신 이번 문제에선 스위핑을 한번 더 추가했습니다.

게시판에 있는 반례도 해보고, 나름대로 반례도 만들어 넣어봤는데 어떤게 문젠지도 모르겠습니다ㅠ.

// 1. X가 큰 순으로, 같으면 Y도 큰 순으로 정렬한다.
// 2. 정렬된 좌표 순서대로 인덱스를 매긴다.
// 3. Y가 큰 순으로, 같으면 X가 큰 순으로 정렬한다.
// 4. 이 주어진 수열에 inversion countin
// ~ 한 점이 왼쪽 위의 점의 갯수를 구하기 위함 ~

// 5. 이제는 X가 작은 순으로, 같으면 Y가 큰 순으로 정렬한다.
// 6. 정렬된 좌표 순서대로 인덱스를 매긴다.
// 7. 다시 Y가 큰 순으로, 같으면 X가 작은 순으로 정렬한다.
// 8. 이 주어진 수열에 inversion countin
// ~ 한 점이 오른쪽 위의 점의 갯수를 구하기 위함 ~

// 9. 그러면 이제 각 좌표마다 왼쪽위의 좌표 갯수와, 오른쪽위의 좌표 갯수를 앎.
// 10. 0번 좌표부터 N - 1번 좌표까지, 왼쪽 위 좌표 갯수 * 오른쪽 위 좌표 갯수 % MOD를
// 총합에 더함.

swc0317   1년 전

확실하지 않은 게 같은 좌표인데

9

-1 1

-1 1

-1 1

0 0

0 0

0 0

1 1

1 1

1 1

다음과 같은 입력이 주어지면

답이 27이 맞나요? 아니면 중복을 제거해서 3이 나와야 하나요?

ehdtodvodl   1년 전

중복제거해서 3인줄 알고 뭐가 틀린지 몰라서 1시간동안 디버깅했는데,

알고보니 중복 포함해서 27로 하는게 맞는 코드였네요…

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