11726번 - 2×n 타일링

1️⃣ DP

 

✏️ 풀이 과정

DFS 대신 다이나믹 프로그래밍을 이용해야 시간초과가 나지 않는 문제입니다.

 

기본적인 아이디어는 수열을 생각하면 됩니다. 3 이상의 n에 대해 방법의 개수를 f(n)이라고 하면

n번째가 만들어지는 경우의 수는 바로 이전에서 1개짜리 타일을 더하는 것과 두 칸 이전에서 2개짜리 타일을 더하는 것 뿐입니다. 그렇기 때문에 f(n) = f(n-1) + f(n-2)가 되고 배열을 통해서 간단하게 계산할 수 있습니다.

 

계산이후 n번째 인덱스를 출력하면 해결됩니다. 이 때 n=1, 2일 때 에러가 발생하지 않도록 주의해야 합니다.  

💻 코드

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

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());
		int[] dp = new int[n+1];
		dp[1] = 1;
		if(n > 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]);
		br.close();
	}
}