2014년 7월 25일 금요일

9461 - 파도반 수열

작년 ACM 본선 문제.

단순한 규칙성 문제라 정답은 아래 정의 하나로 끝나지만 몇가지만 조심하면 된다.

파도반 수열의 N번째 항은 P(N) = P(N-2) + P(N-3); 과 같이 나타낼 수 있다.

하지만 재귀식이므로 DP를 이용해서 꼭! 시간복잡도를 줄여야한다.
댓글 쓰기

게시글 목록