백준 11726번: 2xn 타일링

뭔가 9번째 항을 만드는 데, 이 전의 항들을 이용해서 만들 수 있을 것 같다.

DP로 접근해본다.

일일히 손으로 그려봤다

dp[4]까지 했더니 뭔가 규칙이 보인다.

dp[n] = dp[n-1] + dp[n-2]

근데 이게 진짜일까..?

예제에서 9번째 항은 55라고 했으니 위 규칙을 적용했을 때 dp[9] = 55인지 확인해보면 된다.

dp배열을 계속해서 채워보자면...

dp[5] = 8

dp[6] = 13

dp[7] = 21

dp[8] = 34

dp[9] = 55

규칙이 성립한다.

이를 토대로 코드를 짜보면 아래와 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// 입력
		int n = Integer.parseInt(br.readLine());

		// ArrayIndexOutOfBoundsException 방지
		if(n == 1) {
			System.out.println(1);
			return;
		}
		// 입력받은 크기만큼 DP 배열 생성
		long dp[] = new long[n + 1];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= n; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
		}

		// 출력
		bw.write(String.valueOf(dp[n]));
		bw.flush();
		bw.close();
	}
}