시간 복잡도 질문

Question

안녕하세요 큰돌님 게임 문제를 풀다 시간초과가 나서 질문드립니다. 해당 문제는 50 * 50 배열에 4방향의 경우의 수를 고려해야하니 4 ^ 50의 시간복잡도가 걸릴텐데 최악의 경우 배열의 값이 전부 1이여야할거라고 생각했습니다. 그런데 이때는 순환하는 경우여서 앞서 계산한 시간복잡도보다 훨씬 일찍종료될거라고 판단하였는데요 제가 시간복잡도 계산을 정확하게 한것일까요? 제 코드에서 시간초과가 발생하는 케이스는 어떤게 있을까요? dp가 너무 어렵네요...ㅠㅜ http://boj.kr/5feacce2689b45ca848b64831f7fe0e4 친절한 답변 항상 너무 감사드립니다!

큰돌 · Answer

안녕하세요 sol님 ㅎㅎ 이문제지문을 볼까요? 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다. 이걸기반으로 사실 이 sol님이 질문하신 "시간이 많이 걸리는 예제"를 찾기란 좀 힘이 듭니다. 최악의 경우 배열의 값이 전부 1이여야할거라고 생각했습니다. 그런데 이때는 순환하는 경우여서 앞서 계산한 시간복잡도보다 훨씬 일찍종료될거라고 판단하였는데요 >> 네 맞습니다. 예를 들어 1111 1111 1111 1111 이렇게 1로만 주어진다라고 했을 때 어차피 무한루프를 먼저 찾으면 그대로 종료기 때문에 빠를 것도 같고 그렇기 때문이죠. 그냥 어림잡아서 계산하는게 좋습니다. 말씀하신대로 4^50이 맞습니다. 다만, 실제로 그러한 경우의수를 확인해보면 더 작아질 수 있겠죠. dp가 너무 어렵네요...ㅠㅜ >> 이렇게 생각하면 쉽습니다. 완탐으로 해보자 >> 문제 최대범위를 보니까 시간복잡도 초과할 거 같은데?? >> 이거 배열에 담을 수 있을까? >> dp 이런식으로 하시면 됩니다. 간단하게 생각하세요 ㅎㅎ 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.