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

안녕하세요 지민님 ㅎㅎ

Q1. 이게 dp 인가요..? 아니면 중간에 넣어두신 구현 문제인가요?

-> 구현문제입니다.

Q2. 시간복잡도 계산은 어떻게 하셨나요? 시험도중에 시간복잡도를 계산하기 위해서는 한칸에 존재할 수 있는 나무의 최대 개수를 추정해야한다고 생각이 드는데, 이를 어떻게 추정하셨는지 궁금합니다.

-> 이문제의 경우 단순 구현이라고 판단 + 효율적으로 진행할 부분이 없어보였기 때문에 시간복잡도 계산은 안하고 풀었습니다.

시간복잡도를 추정해보면 k * (springSum + fallWin) 이고, 세부적으로는

springSum : n^2 * (한칸에 있는 나무 최대개수+ nlogn)

fallWin : n^2 (번식할 나무 개수 * 8)

-> 저기서 nlogn 빼고는 맞습니다.

자 그렇다면 시간복잡도를 구해볼까요?

            if(sp[i][j]){// 이 칸에서 나무가 번식해야한다면
                for(int idx=0;idx<8;idx++){ //가을
                    int nr = i+dy[idx];

먼저 각 년마다 나무는 번식할 때 8방향에서 올 수 있습니다.

k x (n^2 x 각 칸의 최대 나무 수를 기반으로 정렬 )

문제의 범위는 다음과 같기 때문에

• 1 ≤ N ≤ 10

• 1 ≤ M ≤ N2

• 1 ≤ K ≤ 1,000

• 1 ≤ A[r][c] ≤ 100

1000 x 100 x 각 칸의 최대 나무 수를 기반으로 정렬이 됩니다.

여기서 각 칸의 최대 나무 수를 계산하는게 포인트입니다.

아마 수강생님이 가장 궁금해하시는게 이부분일 것 같은데요. ㅎㅎ

8^T라고 보면 됩니다. 여기서 T는 번식이 가능한 "5의 배수 나이"를 맞춘 주기입니다.

번식은 5의 배수 나이부터 시작이 가능하니 그 때부터 번식이 시작된다고 가정하고

지금의 칸으로부터 8칸에서 계속해서 나무가 들어온다고 생각하면 됩니다.

여기서 T의 최대값은 K / 5 -> 200입니다.

그렇다면 8^200이라는 결과가 나옵니다.

그러나 나무는 양분을 못받으면 죽는 것을 생각해야 합니다.

8개에서 들어오는 양분의 최대값은 40입니다. 최대 나무의 나이는 10이고 10 x 8 / 2 -> 40입니다.

그리고 해당 칸의 양분이 10이라고 가정해보면 최대양분은 50, 그리고 최대나무수를 생각해보면 나이가 1인 나무가 50개임을 상상할 수 있습니다. 즉, 50개가 넘는 나무가 일시적으로 들어올 수는 있지만 양분을 생각해보면 최대 50개만 살아남기 때문에 50 ~ 64정도라고 볼 수 있습니다.

대략적으로 각 칸의 최대 나무 수는 50이며

1000 x 100 x 50log50이 됩니다.

따라서 최대 시간복잡도는 한 500만 정도 됩니다. 

결과적으로 1억이 넘는다고 계산이 됩니다.

-> 1억이 넘어도 통과하는 문제들은 많습니다.

제 교안내의 시간복잡도 부분 참고부탁드립니다.

새해복 많이 받으세요

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

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

감사합니다.

강사 큰돌 올림.

k :