changu02   1달 전

이제막 알고리즘 공부를 시작한 3학년 학부생입니다.

시간복잡도와 공간복잡도를 많이 고려하지 않고 알고리즘을 짜다보니 이렇게 시간초과가 나타나게 되었습니다.

dfs 재귀방법을 사용하였구요. 여러배열들을 동적할당 해주었는데, 어디서 시간초과가 나타나는지 모르겠습니다.

질문게시판에 올라온 모든 testcase는 완벽하게 수행됩니다. 어디에서 시간을 날렸는지 알려주실수 있으신지요

amugeona   1달 전

해당 소스는 올바르게 돌지만, 빠른 시간안에 돌지 않는다는 의미로 해석됩니다.

먼저 문제의 자료들을 저장할 배열을 정의합니다.

C[n] : n번째 건물이 지어지는 시간

P[n][m] : n번째 건물을 짓기 전에 m번째 건물을 지을 수 없는지의 여부(없으면 1, 있으면 0)


배열이 정의되었을 때, 하나의 함수를 정의해서 고민을 해봅시다.

F(n) : n번째 건물을 지을 수 있게 되는 최소 시간


우리가 구하려는 답은 F(w)가 되겠습니다.

F(n)은 다음과 같이 구할 수 있습니다.

F(n) = max( F[ i ] + C[ i ]  ( i : P[ i ][ n ] 가 1을 만족하는 건물의 번호 )


그런데 F(n)은 정의에 의해서 한번 계산이 완료되면 "다시 구할 필요가 없는" 함수입니다.

따라서 이 부분을 "메모이제이션 기법"을 사용하시면 시간 내에 해결이 가능해지게 됩니다.

궁금하신 점이 있으시면 답변 달아주세요.

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