작성한 질문수 17

0

안녕하세요 sol님 ㅎㅎ

이문제지문을 볼까요?

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

이걸기반으로 사실 이 sol님이 질문하신 "시간이 많이 걸리는 예제"를 찾기란 좀 힘이 듭니다.

최악의 경우 배열의 값이 전부 1이여야할거라고 생각했습니다.

그런데 이때는 순환하는 경우여서 앞서 계산한 시간복잡도보다 훨씬 일찍종료될거라고 판단하였는데요

>> 네 맞습니다.

예를 들어

1111

1111

1111

1111

이렇게 1로만 주어진다라고 했을 때 어차피 무한루프를 먼저 찾으면 그대로 종료기 때문에 빠를 것도 같고 그렇기 때문이죠.

그냥 어림잡아서 계산하는게 좋습니다. 말씀하신대로 4^50이 맞습니다. 다만, 실제로 그러한 경우의수를 확인해보면 더 작아질 수 있겠죠.

dp가 너무 어렵네요...ㅠㅜ

>> 이렇게 생각하면 쉽습니다. 완탐으로 해보자 >> 문제 최대범위를 보니까 시간복잡도 초과할 거 같은데?? >> 이거 배열에 담을 수 있을까? >> dp

이런식으로 하시면 됩니다. 간단하게 생각하세요 ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.