[Programmers] DP : 2 x n 타일링 #12900

문제 링크

2 x n 타일링

문제 조건

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

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

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

• 이 직사각형을 채우는 방법의 수를 구하시오.

• 가로의 길이 n은 60,000이하의 자연수 입니다.

• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

  변수 설명

• n : 직사각형의 가로의 길이 (매개변수)

• memo : memorization을 위한 배열

코드 설명

• 위 사진처럼 n의 경우의 수를 구하기 위해서는 n-1과 n-2의 경우의 수를 더해주면 알 수 있습니다.
  • n-2의 경우의 수에 타일을 가로로 2개 붙여서 추가합니다.
  • n-1의 경우의 수에 타일을 세로로 1개 붙여서 추가합니다.
• 그렇기 때문에 이 문제는 동적계획법으로 풀이하여야 합니다.

  문제 해답

class Solution {
    int [] memo = new int[60001];

    public int solution(int n) {
        int answer = 0;
        memo[0] = 1;
        memo[1] = 1;
        for(int i = 2 ;i <=n;i++) {
            memo[i] = memo[i - 1] + memo[i - 2];
            memo[i] %= 1000000007;
        }
        return answer = memo[n];
    }
}