[백준] 11726 2xn 타일링

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

2020-11-09

---

1. Top-down

import java.util.Scanner;

public class Main11726_1 {
	public static int N, dp[];
	
	public static int solve(int x) {
		if(x == 1) return 1;
		if(x == 2) return 2;
		
		if(dp[x] > 0) return dp[x];
		
		dp[x] = (solve(x-1) + solve(x-2))%10007;
		
		return dp[x];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		dp = new int[N+1];
		System.out.println(solve(N));
	}
}

 

2. Bottom-up

import java.util.Scanner;

public class Main11726 {
	public static int N, dp[];
	
	public static int solve() {
		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;
		}
		return dp[N];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		System.out.println(solve());
	}
}

 

top-down, bottom-up 두 가지 방법으로 풀어봤다.

 

N = 1 : 1개

N = 2 : 2개

N = 3 : 3개

N = 4 : 5개

N = 5 : 8개

.

.

.

N = 9 : 55개

 

의 규칙을 따라가면, dp[N] = dp[N-1] + dp[N-2] 라는 점화식을 도출할 수 있다.