[JAVA] BOJ 9461 파도반 수열
동적 계획법(DP) 문제이다 보니 조금 난이도가 있었다. 파도반 수열을 쭉 써보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37.... 이렇게 이어지는 것을 알 수 있다. 동적 계획법은 수열의 패턴, 즉 점화식을 찾아내는 것이 가장 먼저이기 때문에 패턴을 분석해보니 6번째 숫자부터 f(N) = f(N-1)+ f(N-5)를 따르고 있었다. static long padovan(int N) { if (N_li[N]==0) return N_li[N] = (padovan(N-1) + padovan(N-5)); return N_li[N]; } 이런 식으로 재귀 함수를 구성해주면 되고 N_li라는 배열은 메모 이제이 션(Memoization)을 구현하기 위해 만들어준 배열이다..
