프로그래머스: 2xn 타일링 [JAVA]

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 점화식 dp[n] = dp[n - 1] + dp[n - 2]을 적용해 연산

 해당 문제는 점화식을 발견만 하면 되는 문제이다. 가로 길이가 n인 타일을 채우기 위해선 이보다 작은 가로 길이를 찾은 개수들에서 몇 개를 더하면 되는데, 왜냐하면 한 번에 가로 길이를 +1만 시키려면 2x1 타일을 하나를 길게 추가하는 방법이고, 한 번에 가로 길이를 +2만 시킬 수 있는 방법은 2x1 타일 2개를 가로로 길게 2개를 추가하는 방법 뿐이기 때문이다. 이 외에는 모두 이전 방법들과 중복의 위험이 있기 때문에, 최종적으로 함수를 f(n) = f(n-1) + f(n-2)라고 얻을 수 있다.

 그러기에 n = 1인 경우 값 1, n = 2인 경우 값 2를 채워넣고, 동적 프로그래밍 방식을 적용해 dp 배열을 만든 후 차례차례 연산을 진행하면 된다. 이 때 값이 1,000,000,007이 넘을 수 있으니 연산 결과를 미리 (n % 1,000,000,007)을 진행 해 저장하는 방식으로 코드를 작성했다.

 

class Solution {
    public int solution(int n) {
        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {//dp 적용
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }

        return (int) dp[n];
    }
}

결과