import java.math.BigInteger;
class Solution {
public int solution(int n) {
if (n % 2 == 1) return 0;
BigInteger[] dp = new BigInteger[n + 1];
dp[0] = new BigInteger("1"); dp[2] = new BigInteger("3");
BigInteger four = new BigInteger("4");
for (int i = 4; i <= n; i += 2) {
dp[i] = dp[i - 2].multiply(four).subtract(dp[i - 4]);
}
return dp[n].remainder(new BigInteger("1000000007")).intValue();
}
}
규칙을 못 찾고있다가 어떤 분의 풀이를 보고 처음 몇 개는 완전탐색을 통해서 값을 구한 후 규칙을 찾는 방식을 통해 규칙을 찾게되었다.
하지만 그 뒤에 나머지 연산에서 막혀 BigInteger를 사용하게되었다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges