인프런 커뮤니티 질문&답변

안녕하세요 큰돌님!

해당 문제의 시간 복잡도 관련된 질문이 있어서 여쭤봅니다.

3-O 번 문제에 대해서 어떤 로직을 쓸 지 고민하다가,

사다리 3개 조작, 사다리 내려가기 << 이렇게 2 가지 로직이 필요 하다고 생각했습니다.

그래서 제가 계산한 바는,
사다리 3개 조작 : 300 C 3
사다리 내려가기 : 30 * 10

이 둘의 로직이 동시에 일어나야 한다고 생각해서,
300 C 3 * (30 * 10) 라고 결론 냈습니다.

http://boj.kr/475effafef89456687b5176ac5dcf21c
(정답코드 링크)

그런데, 강의를 보니까

선생님은 300 C 3 만 언급하셧는데요. 이 부분이 이해가 되지 않습니다.

정답코드의 재귀 함수만 보더라도, 2중 for문 안에서 go()가 호출되는데, 이런 경우는 사다리 내려가기에 대한 시간복잡도가 영향을 받지 않는건가요?

// 경우의 수를 두면서 재귀.
    for(int i = here; i <= h; i++){
        for (int j = 1; j <= n; j++)
        {
            // 이미 존재하는 경우는 예외
            if(line[i][j] || line[i][j-1] || line[i][j+1]) continue;
            
            // 경우의 수 추가
            line[i][j] = 1;
            go(i, cnt + 1);
            line[i][j] = 0;
        }
        
    }

질문이 좀 길어졌네요. 정리하면 이렇습니다.

Q1. 제가 계산했던, 사다리 조작 * 사다리 내려가기 에 대한 시간 복잡도 계산은 틀렸나요? 틀렸다면 어디서 로직 오류가 있는건가요?

Q1-1. 혹시, 제가 계산했던 시간 복잡도에서,
300 C 3 + (30*10) 으로 계산해도 무방한가요?

Q2.선생님은 왜 300 C 3 이라고만 계산하셨나요?
완탐이든/백트래킹이든 재귀로 탐색(?)해야 하는 건 알겠는데, go() 함수가 호출되는 2중 for문에 대한 시간복잡도는 계산 안하셨는지 모르겠습니다.

답변 기다리고 있겠습니다!

감사합니다~!!