[백준] 11726 2×n 타일링 - Dynamic Programming / Java

• 문제 링크

11726번: 2×n 타일링

 

• 풀이 과정

문제에서 제시된 직사각형의 세로의 길이는 2로 고정되어 있으므로 가로의 길이만 고려하여 점화식을 구한다.

즉 n 을 1 또는 2의 합으로 나타내는 방법의 수를 구하는 문제로써 예시를 나타내면 아래와 같다.

2 = (1 + 1) (2), 3 = (1 + 1 + 1) (1 + 2) (2 + 1), 4 = (1 + 1 + 1 + 1) (1 + 1 + 2) (1 + 2 + 1) (2 + 1 + 1) (2 + 2)

 

이때 4를 만드는 경우의 수는 2의 모든 경우의 수에 2를 더한 것 + 3의 모든 경우의 수에 1를 더한 것이므로

이에 대한 점화식을 dp배열을 활용한 코드에 적용하면 dp[i] = dp[i - 1] + dp[i - 2] 이 성립한다.

 

추가로 ArrayIndexOutOfBounds 에러를 방지하기 위하여 dp[0] = dp[1] = 1 로 초기화,

자료형 오버플로우를 방지하기 위하여 각 dp 배열에 값을 저장할 때마다 % 10007 연산을 수행한다.

 

• 풀이 코드

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

public class Main {

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

		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];

		dp[0] = dp[1] = 1;

		for (int i = 2; i < n + 1; i++)
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;

		bw.write(dp[n] + "\n");
		bw.flush();
	}

}