[Java/자바] 프로그래머스 Lv2 - 2 x n 타일링(DP 알고리즘)

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다.

이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다.

타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

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

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

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

 

제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

입출력 예

n	result
4	5

 

---

Solution.java

이 문제는 DP를 활용하여 쉽게 풀이 할 수 있는 문제입니다.

왜 DP를 이용할 수 있는지 다음을 통해 알아봅시다.

그림을 보면, n이 1, 2, 3, 4 ~ 로 커질 때마다 경우의 수는 다음과 같습니다.

n	1	2	3	4
경우의 수	1	2	3	5

 

n이 3일 때 경우의 수는, n이 2일 때의 경우의 수 2 + n이 1일 때의 경우의 수 1 을 더한 값과 같습니다.

n이 4일 때 경우의 수는, n이 3일 때의 경우의 수 3 + n이 2일 때의 경우의 수 2 을 더한 값과 같습니다.

 

그러면 위 결과를 바탕으로

DP의 조건인 부분 반복 문제, 최적 부분 구조가 성립되며 피보나치 수열 같이 이런 식을 만들 수 있습니다.

arr[n] = arr[n - 1] + arr[n - 2]

이제 이 DP점화식을 이용하여 문제를 풀어 봅시다.

 

 

만약 DP 알고리즘에 대한 설명이 필요하다면 아래 링크를 참고해주세요.

[알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법

 

정답 코드

public class 타일링 {
    public static void main(String[] args) {
        System.out.println(solution(4));
    }

    public static int solution(int n) {
        int[] arr = new int[n];
        arr[0] = 1; // 세로
        arr[1] = 2; // 가로

        // arr[2] 부터 시작
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2] % 1000000007;
        }

        return arr[n - 1];
    }
}