[BOJ/JAVA] 백준 11727번 : 2 x n 타일링 2

ㅠㅒㅓ

---

 

• 생각

다이나믹프로그래밍 문제이다. 점화식의 생성 계기는 dp(N) 을 구할때 dp(N-1) + dp(N-2)에서 dp(N-2) 즉 2*(N-2)의 직사각형을 구하는 방법은 마지막에 2*2타일을 채우는 방법, 1*2 타일로 채우는 방법 2가지가 있으므로 dp(N) = dp(N-1) + dp(N-2) *2가 된다

 

• 코드

정답 코드 : 1칸일 땐 세로로 1개, 2칸일 땐 2x2한개 2x1 두개 총 2개, N-1번의 칸에 타일 한개를 추가하는 방법과 N-2번의 칸에 2개 짜리 타일을 추가하는 방법으로 점화식을 세움.

 

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		if (N == 1) {
			System.out.println(1);
			System.exit(0);
		}
		if (N == 2) {
			System.out.println(3);
			System.exit(0);
		}
		int[] dp = new int[N + 1];
		dp[1] = 1;
		dp[2] = 3;
		for (int i = 3; i <= N; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]*2) % 10007;
		}
		System.out.println(dp[N]);
	}
}

 

다시 풀어본 코드 : N이 1, 2인 경우 반복문으로 들어가게되면 런타임이 뜨는데 해당 경우를 생각을 안해서 런타임이 한번 떴다. 또, N이 1인경우 dp[2]를 들어갈 경우 런타임이 뜬다. 

 

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

public class Main {
	private static int N;
	private static int[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(dp[N]);
	}
	
	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		dp = new int[N + 1];
		
		dp[1] = 1;
		if(N == 1) return;
		dp[2] = 3;
		if(N == 2) return;
		for (int i = 3; i <= N; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]*2) % 10007;
		}
	}
}