park780172   10달 전

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의



원래 처음에 풀었던 제 코드(http://boj.kr/97b6290ab87740c8b3d8b415e797605d)는 시간이 968ms나 걸렸습니다.

(처음 풀었던 코드의 의도는 한 점에 대해 여러 for문을 사용하여 직사각형 내에 존재하는 1의 합 구하기입니다. -1은 따로 계산.)

이유는 50*50이므로 이것을 백트래킹으로 하기에는 당연히 오래걸렸을 것이라고 생각했습니다.

그래서 어쩔 수 없이 시간이 빠른 다른 분의 코드를 봤더니 공식(?)을 활용하시거나 dp, knapsack, memoization 등으로 접근하셨더라구요. 

하여튼 공식(첨부한 코드의 66, 69번 째 줄)을 제 코드에 적용하여 제출했더니 0ms가 나왔습니다.

무려 50*50을 백트래킹하기에는 오래 걸릴 것이라고 생각했었는데 0ms가 나와서 제가 생각한 시간 복잡도(2또는 n!)와는 다른 것 같습니다.

제 코드의 시간 복잡도가 어떻게 되는지 궁금합니다.

첨부한 코드가 0ms 나온 코드입니다.

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