[Java] 프로그래머스 Lv2 - 2 x n 타일링

🔗 문제링크

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

📂 분류

DP

💡 풀이

2 x n 타일링 문제는 메모이제이션을 대표하는 문제이다.

이 문제는 bottom-up 방식과 top-down 방식 두 가지로 해결할 수 있는데, 나는 bottom-up 방식으로 접근하여 문제를 해결했다.

 

접근 방식

• n이 1일 경우 가로로만 배치할 수 있기 때문에 배치할 수 있는 경우는 한 가지만 존재한다.
• n이 2일 경우 가로로 배치하고 세로로도 배치할 수 있기 때문에 배치할 수 경우는 두 가지가 존재한다.
• n이 3일 경우는 n == 1일 때 배치할 수 있는 가지 수와 n == 2일 때 배치할 수 있는 가지 수를 더한 값과 같다.
• 따라서 점화식은 아래와 같이 나오게된다.

 tiles[i] = tiles[i - 1] + tiles[i - 2]

💻 코드

public class Solution {

    private static final int MOD = 1000000007;

    public int solution(int n) {
        int[] tiles = new int[n + 1];
        
        tiles[1] = 1;
        tiles[2] = 2;

        for (int i = 3; i <= n; i++) {
            tiles[i] = (tiles[i - 1] + tiles[i - 2]) % MOD;
        }

        return tiles[n];
    }
}