[백준] 11726번 : 2×n 타일링

문제

 

 

접근 방식

강의에서 설명해 주기 전까진 DP 문제일 줄은 생각도 못하고 있던 문제다...

 

 

일단 위와 같은 타일을 채워야 할 때

가장 위의 칸부터 채우는 경우를 살펴 보면

 

 

2*1 타일은 이렇게 하나를 둘 수 있는데

 

 

그러면 정확히 2*(n-1) 칸이 남게 된다.

 

 

1*2 타일의 경우에는 어차피 한 층에 1*2 타일을 쌓으면

다른 한 층도 무조건 1*2 타일을 쌓을 수밖에 없으니

2*(n-2) 칸이 남게 된다.

 

 

결국 이 한 칸에 올 수 있는 경우의 수는 (n-1) + (n-2)에 해당한다.

 

눈치가 빠른 사람은 이 공식을 어디서 많이 봤다고 생각할 수도 있는데

피보나치수열과 똑같은 공식이다.

 

이제 문제를 풀 수 있는 식은 구했으니

DP 테이블을 만들어야 하는데

간단하게 i일 때 경우의 수를 저장할 DP [N]으로 만들어주면 된다.

 

테이블의 초기값은 1일 때는 1, 2일 때는 2로 지정해 준 뒤에

3부터 반복문을 돌면서 DP [i-1] + DP [i-2]를 구한 후에

문제에서 요구한 대로 10007로 나눠 주면 된다.

 

풀이

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());

		if (n == 1) {
			System.out.println(1);
			return;
		}

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

		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]);
	}
}