[프로그래머스] 2 x n 타일링

문제설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

해결 방법

동적 계획법(DP, Dynamic Programming)을 활용해 해결할 수 있는 문제.

 

가로의 길이가 n일 때 나올 수 있는 경우의 수를 D[n]이라 할 때, 아래와 같이 경우의 수가 나오게 된다.

 

D[1] = 1

 

D[2] = 2

 

D[3] = 3

 

D[4] = 5

 

...

 

이를 점화식으로 세우면 D[n] = D[n-1] + D[n-2]가 되고 

 

이를 활용해 가로 길이 n일 때 경우의 수를 찾는다.

 

JAVA

package programmers;

import java.util.*;

public class p_12900 {
	public static int solution(int n) {
		int answer = 0;
		int[] dp = new int[n+1];
		dp[1] = 1;
		dp[2] = 2;
		for(int i = 3; i <= n; i++) {
			dp[i] = dp[i-1] + dp[i-2];
			dp[i] %= 1000000007;
		}
		answer = dp[n];
		return answer;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int r = solution(n);
		System.out.println(r);
	}
}