[백준/Java/DP] 11726 2xn 타일링 (feat. 다이나믹 프로그래밍)

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

# 입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

# 출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

 

 

---

 

 

 

이 문제는 "다이나믹 프로그래밍" 기법을 사용하여 해결할 수 있다.

 

다이나믹 프로그래밍이란,

큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 것으로 쉽게 말해 답을 재활용하는 기법이다.

성립되기 위한 두가지 조건은 다음과 같다.

• Overlapping Subproblem
  큰 문제를 작은 문제로 나누었을 때, 작은 단위로 나누어진 문제들은 같은 정답의 형태가 되어야 한다.
• Optimal Substruction
  작은 부분에서 구한 최적의 답으로 큰 문제의 최적의 답을 구할 수 있어야 한다.

 

다시 문제로 돌아와 경우의 수를 하나씩 살펴보자.

 

 

 

n = 4 까지 그린 후 확인해보면 일정한 패턴이 반복됨을 알 수 있다.

노란색으로 체크된 n - 1 타일에 세로 타일이 하나 추가된 모습이고,

파란색으로 체크된 n - 2 타일에 가로 타일이 두개 추가된 형태를 가지고 있다.

 

즉, dp[n] = dp[n - 1] + dp[n - 2] 라는 점화식을 갖게 된다.

 

 

풀이

import java.io.*;

public class Main {
	public static void makeTile(int n) {
		int[] dp = new int[1001];
		dp[1] = 1; dp[2] = 2;

		for(int i = 3; i <= n; i++)
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
		
		System.out.println(dp[n]);
	}

    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		makeTile(Integer.parseInt(br.readLine()));
	}
}

 

 

© 참고

https://www.acmicpc.net/problem/11726

https://girawhale.tistory.com/33

11726번: 2×n 타일링