2414번 - 게시판 구멍 막기
가설 : 직선으로 연속한 구멍을 테이프 하나로 막으며, 장애물인 "구멍이 아닌 공간" 을 테이프가 넘을 수 없으므로, 구멍이 빈공간이고 구멍아닌곳이 장애물인 룩 배치하기 문제와 동일하다고 볼 수 있다
라고 세우고 룩 코드를 제출햇는데 패스하네요.
다만 룩은 방향이 두개고, 이 테이프는 방향이 하나인데 동일한 문제라고 판단할 근거가 좀 부족하다랄까요
룩 배치하기는 이분 그래프에서 최대 매칭의 크기를 구하는 것이고
이 문제는 이분 그래프에서 최소 정점 덮개의 크기를 구하는 건데
쾨닉의 정리에 의해 둘은 같습니다.
댓글을 작성하려면 로그인해야 합니다.
wlssud0701 3년 전 1
가설 : 직선으로 연속한 구멍을 테이프 하나로 막으며, 장애물인 "구멍이 아닌 공간" 을 테이프가 넘을 수 없으므로, 구멍이 빈공간이고 구멍아닌곳이 장애물인 룩 배치하기 문제와 동일하다고 볼 수 있다
라고 세우고 룩 코드를 제출햇는데 패스하네요.
다만 룩은 방향이 두개고, 이 테이프는 방향이 하나인데 동일한 문제라고 판단할 근거가 좀 부족하다랄까요