[백준] 11726번: 2xn 타일링 (Java/자바)

 

문제

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

문제풀이

전형적인 DP 문제이다. 이 문제는 처음에 봤을 때 완전 탐색으로 풀어야하나? 이렇게 고민되기도 하지만, 그렇게 된다면 구현 자체도 복잡할뿐만 아니라 2의 N승까지의 복잡도를 갖기 때문에 시간내에 풀 수 없게된다. 천천히 생각해보면 N = 1, N = 2, N = 3, ... 일때의 상황을 그려보고 점화식으로 풀이가 가능한 형식임을 눈치채야한다.

 

점화식은 dp[N] = dp[N-1] + dp [N-2] 이다.

dp[1] = 1 // N == 1 일 때 가능한 조합은 1가지 뿐이다.

dp[2] = 2 // N == 2 일 때 가능한 조합은 2가지 이다. (2x1 을 2개 쌓거나, 1x2를 2개 쌓거나)

dp[3] = 3 // N == 3 일 때 가능한 조합은 3가지 이다. (2x1 을 3개 쌓거나, 1x2 1개, 2x1 2개를 위치를 바꿔 놓는 방법 2가지)

dp[4] = 5 // N == 4 일 때 가능한 조합은 5가지 이다.

.

.

.

 

여기서, 보면 알겠지만 dp[4] = dp[3] + dp[2] = 3 + 2 = 5

dp[3] = dp[2] + dp[1] = 2 + 1 = 3

dp[2] = dp[1] + dp[0] = 1 + 1 = 2 ( N = 0 인 경우는 아무것도 없는 상태 한가지이므로 1로 초기화)

이므로 점화식을 알 수 있다. 이와 같은 방법으로 풀게된다면 매우 쉽게 풀 수 있음을 알 수 있다.

 

소스코드

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

public class Main {
	public static int N;
	public static final int MAX = 10_007;
	public static int[] dp;


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		dp = new int[N + 1];
		
		// N == 1
		dp[0] = 1;
		dp[1] = 1;
		
		System.out.println(solve(N));
	}
	
	public static int solve(int n) {
		if(dp[n] > 0) return dp[n] % MAX;
		dp[n] = (solve(n-1) + solve(n-2))%MAX;
		return dp[n];
	}
}