17471번 - 게리맨더링
문제 크기가 작은 관계로 bfs로 두번돌릴 수 있다고 생각한게 오산이었을까요??
nC0과 nCn은 논외로 치고
nC1부터 nCn-1까지 모든 경우를 상정해놓고
조합이 완성되었을 때 방문배열 가운데 어느 하나라도 방문처리되지 않은 게 있다면
다음 경우의 수를 따지도록 하고,
만일 방문처리가 잘 이루어졌다면(선거구1,선거구2가 잘 떨어짐)
그 때 최솟값을 갱신하는 방식입니다.
방문 배열을 여러번 초기화를 하는데 어떤 부분을 초기화하느냐에 따라 반례가 통과되는게 있고 아닌게 있습니다 ㅋㅋㅋ ㅜㅜㅜㅜㅜㅜ
근본적으로 어떤 부분이 문제인지 모르겠습니다.
도와주시면 정말 감사합니다ㅜㅜㅜㅜ 며칠 동안 계속 이 문제만 고민하는데 정말 모르겠습니다ㅜㅜ
댓글을 작성하려면 로그인해야 합니다.
celestial 3년 전
문제 크기가 작은 관계로 bfs로 두번돌릴 수 있다고 생각한게 오산이었을까요??
nC0과 nCn은 논외로 치고
nC1부터 nCn-1까지 모든 경우를 상정해놓고
조합이 완성되었을 때 방문배열 가운데 어느 하나라도 방문처리되지 않은 게 있다면
다음 경우의 수를 따지도록 하고,
만일 방문처리가 잘 이루어졌다면(선거구1,선거구2가 잘 떨어짐)
그 때 최솟값을 갱신하는 방식입니다.
방문 배열을 여러번 초기화를 하는데 어떤 부분을 초기화하느냐에 따라 반례가 통과되는게 있고 아닌게 있습니다 ㅋㅋㅋ ㅜㅜㅜㅜㅜㅜ
근본적으로 어떤 부분이 문제인지 모르겠습니다.
도와주시면 정말 감사합니다ㅜㅜㅜㅜ 며칠 동안 계속 이 문제만 고민하는데 정말 모르겠습니다ㅜㅜ