[programmers] 2 x n 타일링 - Java

2 x n 타일링

문제 설명

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

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

제한사항

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

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

입출력 예

입출력 예 설명

solution.java

class Solution {
    public int solution(int n) {
        // mod 값
        int MOD = 1_000_000_007;

        // n이 1 또는 2일 경우 예외처리
        if (n == 1) return 1;
        if (n == 2) return 2;

        // 2 x n 바닥을 채우는 방법을 저장하는 dp 배열
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        // 반복으로 dp 배열 채우기
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        return dp[n];
    }
}

핵심 키워드

• n-1과 n-2의 결과를 합치면 n일때의 값이 나오므로, 이 값에 MOD로 나머지 연산을 한 값을 구하면 정답이 된다.

결론!