프로그래머스 - 2 x n 타일링 문제 (자바)

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

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

타일 채우기 문제로 dp를 이용해서 풀었다.

 

n = 1 이면 1개 (세로 1)

n = 2 이면 2개 (세로 2, 가로 2)

n - 3  이면 3개 (세로 3, 세로 1 가로 2, 가로2 세로 1)

 

n = 3 인 경우를 보면

n = 1일때 가로2개와 세로 2개 더 세우는 경우

n = 2일때 세로 타일을 하나더 세우는 경우

두 경우의 합에 겹치는 경우를 빼면 된다.

 

class Solution {
    public int solution(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] * 2 + dp[i - 1] - dp[i - 2]) % 1000000007;
        }
        int answer = dp[n];
        return answer;
    }
}