hyunynim   5년 전

아이디어는 다음과 같습니다.

먼저 그래프를 입력받으면서 0의 개수를 셉니다.

이때 벽은 항상 3개가 세워질 것이므로 해당 카운트 할 변수를 -3으로 초기화하여 셉니다.

이후 3개의 벽을 세울 수 있는 모든 경우에 수(wall())에 대하여 체크(check())합니다.

체크하는 방식은 그래프가 2인 곳에서 시작하여 벽을 만나기 전까지 0의 개수를 세서 총 0의 개수에서 이를 빼준 답을 구합니다.

이러한 방식으로 계산할 경우 시간복잡도가O((NM)^4) 라고 생각하여 시간내에 해결 되리라 생각했는데 TLE는 커녕 WA를 받네요.

반례를 찾아보려고 이것저것 넣어서 시도해봤는데 찾기가 참 힘드네요.

조언좀 해주시면 감사하겠습니다.

넣어본 TC들은 다음과 같습니다.

맨 처음 8 8 에 0으로 꽉 채워져 있는것은 밑에서 TC를 쉽게 만들기 위해 만들어 놓은거라 output을 따로 쓰지 않았습니다.

14502_TC.txt

Green55   5년 전

일단 로컬에서만 돌아가는것 같습니다. 채점 환경과 같은 gcc 7.3.0에서 돌려보니 예제가 하나도 돌아가지 않습니다.

문제의 주 원인은 graph 배열을 bool로 선언하고 2를 저장하는것 같습니다. int로 하셔야합니다.

hyunynim   5년 전

답변 감사합니다. 왜 저걸 못찾아가지고 한참을 고생했을까요...

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