sgc109   7년 전

시간복잡도는 O(N^3) 정도인것같은데 시간초과가나는게.. 정답을 제대로 찾는데 오래걸린다기보다

제대로 정답을 구하지도못하고 제일 바깥에있는 for(int t = 0; ; ++t) 여기를 못빠져나오는경우가있는것같은데..

도움부탁드립니다.

각 섬 별 번호를 부여하고 한칸씩 모든 섬을 확장시키면서 닿을때의 t 값을 바탕으로 계산하여 답을 냈습니다.

그리고 새로넓혀진 칸과 기존 섬의 영토를 구분하기위해 새로넓혀진 칸은 섬 번호에 - 를 붙여서 구분하고 모든 땅의 확장작업이 끝나면

모든 칸을 돌며 음수를 양수화 시켜줬습니다.

@dlwodnsdl

dlwodnsdl   7년 전

제가 자바로 코딩하다보니 c언어를 보는거는 익숙하지는 않은데, 일단은 for구문에서 전체를 뒤집는 작업을 하기보다는 3중배열을 사용하여 각각에 대해서 언제 육지로 되었는지를 기록해주는 편이 나을거 같습니다. 그리고 저렇게 짜시면 아마 2t거리밖에 안되는 경우에도 2t+1로 끝나는 경우가 발생할 것 같은데 c언어를 잘몰라서 확신은 못하겠네요.

sgc109   7년 전

@dlwodnsdl 

답변감사합니다. 음.. 어차피 시간복잡도는 O(N^3) 이면 널널하고 3중배열로 하는것과 이렇게하는것의 시간복잡도도 같아서 AC나올게 WA 나오진 않을거라생각해서 그냥 저렇게했습니다 ㅎㅎ

거리는 아무리생각해도 맞게 계산하는것같은데 혹시 간단한 반례하나만 들어주실수있으신가요?

제가 저 소스를 제출 했더니 시간초과가 나왔는데 첫번째 for(int t ... 여기 반복문안에 t=300 일때 그냥 0을 출력하고 프로그램을 종료하도록 코드를 수정해서 제출해봤더니 틀렸습니다. 가 나왔습니다.

그런데 만약 애초에 제때 이 반복문에서 벗어난다면 섬이 두개만있고 가장 멀리떨어져있다고해도 t=100 쯤에서 끝나야하는데 t가 300일때의 동작을 추가했다고 결과가 달라진다는건 t가 300까지 돌고있다는 것으로 해석했고

일단 그래서 시간초과가 시간복잡도의 문제라기보다는 답을 출력하고 프로그램을 종료하는 부분의 조건부가(제때 종료할땐 제대로된 값을 출력하는지 아닌지는 아직 모르겠지만) 문제가 있다고 판단이 되었습니다.. 근데 어디가 문제가 있는지 찾질못하고있네요ㅠㅠ

dlwodnsdl   7년 전

1 0 0 0

0 0 0 0

0 0 0 0

1 0 0 0

여기서 제대로 나오나요? 이렇게 하면 3행 1열에서 끝나서 거리가 2가 출력되야 하는데 출력되지 않을 것 같네요.


dlwodnsdl   7년 전

이렇게 간척작업과 거리체크를 따로 하시는 경우에는 들어가는 순서에 따라서 간척이 되서 거리체크가 되어야 하는 경우에도 거리체크가 안되는 경우가 발생할겁니다. 어차피 간척작업이 진행되는 경우에만 땅이 만나게 되니까 간척을 진행하고 간척한 땅에 대해서 거리체크를 하시는 편이 나을것 같습니다.

sgc109   7년 전

@dlwodnsdl 2 맞게 출력되네요!

sgc109   7년 전

@dlwodnsdl 원래 질문은 왜 TLE 가 나는지였지만 .. 어쨋든 답변 감사드립니다!

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