[프로그래머스] 3 x n 타일링 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/12902#

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

 

풀이

전형적인 dp문제로 규칙을 찾아서 점화식을 세워서 풀 수 있다. 

아래 문제는 조금 더 쉬운 버전이다.

2021.10.29 - [Problem Solving/Programmers] - [프로그래머스] 2 x n 타일링 (Java)

[프로그래머스] 2 x n 타일링 (Java)

 

나의 경우, 이런 문제는 생각만 해서는 머릿 속으로 잘 안그려진다.

일단 무작정 그려보았다. 

 

N = 1일 때, 

물론 N이 1일 때 완전하게 모든 공간에 타일 배치를 하는 것은 불가능 하다. (세로 길이가 3이기 때문에)

그럼에도 불구하고 1*3 이라는 공간에 타일을 배치하는 방법을 그려보았다. 

위, 아래로 2가지 경우의 수가 있다.

N = 2일 때, 

3가지 경우의 수가 있다. 

N = 3일 때, 

N이 홀수일때는 완전하게 모든 공간을 가득 채우는건 불가능하다. 

다만 패턴을 찾기 위해 아래와 같이 경우의 수를 도출해보았다. 

N이 홀수일 때: dp[N] = dp[N-1]*2 + dp[N-2];

• N이 2일 때의 패턴에다가 세로 타일을 위 아래로 하나씩 붙임
• N이 1일 때의 패턴에다가 가로 타일을 세 개 연달아 붙임

N = 4일 때,

그려놓고 보니, N이 3일 때와 N이 2일 때의 패턴에다가 타일을 붙인 것을 알 수 있었다.

따라서 아래와 같이 식을 도출할 수 있었다.

N이 짝수일 때: dp[N] = dp[N-1] + dp[N-2];

 

점화식

N이 홀수일 때: dp[N] = dp[N-1]*2 + dp[N-2];

N이 짝수일 때: dp[N] = dp[N-1] + dp[N-2];

 

전체 패턴

 

소스코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int mod = 1000000007;
        int[] dp = new int[n+1];
        dp[1] = 2;
        dp[2] = 3;
        for(int i = 3; i <= n; i++){
            if(i%2 == 0){
                //짝수
                dp[i] = dp[i-1]%mod + dp[i-2]%mod;
            } else {
                // 홀수
                dp[i] = dp[i-1]*2%mod + dp[i-2]%mod;
            }
            dp[i] = dp[i]%mod;
        }
        return dp[n];
    }
}