[알고리즘][Java] 백준(BOJ) 11727 2Xn 타일링 2_자바

 

DP

11727 2Xn 타일링 2    https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• n을 Scanner를 이용하여 입력받는다.
• 배열의 크기가 n+1인(인덱스가 0 ~ n 까지) 배열을 선언한다.
• 그리고 2 x n번째 직사각형을 타일로 어떻게 채울 수 있는가를 고민해야 한다.
• 먼저 2 x 1의 경우 2 x 1의 경우 1가지이다.
• 2 x 2의 경우 2 x 1을 2개 붙이는 경우, 1 x 2를 2개 붙이는 경우, 2 x 2 1개로 3가지이다.
• 2 x 3의 경우 2 x 2에 (2 x 1을 붙이는 경우) + 2 x 1에 (1 x 2를 2개 붙이는 경우 + 2 x 2를 1개 붙이는 경우)로 3(2 x 2에 2 x 1을 붙이는 경우) + 1(2 x 1에) X 2(1 + 1) = 5가지이다.
• 이와 같은 논리로 2 x n = (2 X (n-1)의 경우의 수) + (2 X (n-2)의 경우의 수 X 2) 식을 발견할 수 있다.
• 위의 식을 출력하는 코드를 작성하면 된다.
• 이때, 방법의 수를 10,007로 나눈 나머지를 출력하는 조건을 잊으면 안 된다.

 

<코드>

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		int[] dp = new int[n+1];
		dp[0] = 1;
		dp[1] = 1;
		for (int i=2; i<=n; i++) {
			dp[i] = (2*dp[i-2] + dp[i-1]) % 10007;
		}
		
		System.out.println(dp[n]);

	}

}

 

 

 

 

 

 

같은 문제 파이썬으로 푸는 방법

2021.01.06 - [Algorithm/백준 알고리즘_Python] - [알고리즘][Python] 백준(BOJ) 11727 2xn 타일링 2_파이썬

[알고리즘][Python] 백준(BOJ) 11727 2xn 타일링 2_파이썬