짧게 덧붙이자면 위에 말씀해주신 것처럼 5 구역의 경계선을 먼저 그려줘야 1 ~ 4 구역을 구할때 넘어가는 일이 없습니다.
"5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다."
문제에 적혀 있듯이 5번 구역을 먼저 정하지않고 조건만 보면 1 - 4구역과 5번의 영역이 겹친다는것을 알 수 있습니다.
17779번 - 게리맨더링 2
짧게 덧붙이자면 위에 말씀해주신 것처럼 5 구역의 경계선을 먼저 그려줘야 1 ~ 4 구역을 구할때 넘어가는 일이 없습니다.
"5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다."
문제에 적혀 있듯이 5번 구역을 먼저 정하지않고 조건만 보면 1 - 4구역과 5번의 영역이 겹친다는것을 알 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
rlawowns000 4년 전 4
제 로직은 간단하게 말하자면,
// 틀렸던 로직
으로 했었습니다. 위와 같은 로직을 썼던 이유는 최대한 간단하게 풀기 위해서였지만 틀렸습니다.
위와 같은 반례를 실행하게 되면, 저 같은 경우는 107이라는 오답이 나왔습니다. (정답은 158)
이유를 알기 위해 구역을 출력해보면 아래와 같은 경우가 보입니다.
잘 보시면, 중간에 'B'라는 구역이 띄어져서 발생하는 것을 보실 수 있습니다.
바로 제 코드가 틀린 이유를 보여주는 예시가 될 수 있습니다. 사각형 단위로 색칠하고 5구역을 덮어쓰면 된다고 생각하였으나 5구역이 위와 같이 얇을 경우에는 튀어 나오는 현상이 발생했습니다. 따라서 위와 같은 부분을 처리해주고 나서야 통과가 되었습니다.
다른 분들은 아마도 잘 하셨겠지만 저는 이 부분에서 한참 헤메었습니다. 다른 분 코드랑 같이 돌려서 겨우 반례를 구하여 오류를 찾을 수 있었네요...
저와 같은 경우라면 이 글이 도움이 되길 바라겠습니다.
틀린 코드의 부분을 첨부하겠습니다. 아마 제 로직이라서 필요는 없을 것 같은데 저는 저 부분을 변경하여 해결했었습니다.
정답 전체 코드 : http://boj.kr/dff3e3b575694b22...