BOJ_S3_11727

📁 [S3_11727] 2*n 타일링 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		int[] dp = new int[N+1];

		dp[0] = 1;
		dp[1] = 3;
		for(int i=2; i<N; i++) {
			dp[i] = (dp[i-1] + 2*dp[i-2]) % 10007;
		}

		System.out.println(dp[N-1]);
	}
}

🤔 나의 생각

문제를 보고 고민하다가 먼저 몇개를 나열해보았다.
원래 방법을 찾지 못할때는 직접 해보는게 최고..

n =1,2,3 까지 나열해보았는데 규칙을 찾을 수 있다.
dp[i] = dp[i-1] + 2*dp[i-2]
이 공식을 활용해서 문제에서 10007로 나눈 나머지값을 구하면 된다.