[프로그래머스/Lv. 2] 3 x n 타일링 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static final int mod = 1_000_000_007;
    
    public int solution(int n) {
        int answer = 0;
        
        long[] dp = new long[5001]; // int형으로 하면 틀림
        dp[0] = 1;
        dp[2] = 3;
        
        for(int i = 4 ; i <= n ; i += 2) {
             dp[i] = dp[i - 2] * 3;        // 일반 모양의 경우의 수
 
             for(int j = i - 4 ; j >= 0 ; j -= 2) {    // 🔔 2가지 특수 모양 추가 처리하기
                 dp[i] += dp[j] * 2;
             }
 
             dp[i] %= mod;
        }
        
        return (int)dp[n];
    }
}

 

 

🧩 해결 아이디어

• DP

- n이 홀수인 경우, 타일을 모두 채울 수 없으므로 dp[n] = 0.

- n이 짝수인 경우, 이전 n이 만들 수 있는 경우의 수 + 특수 모양 만드는 경우의 수를 모두 고려해야 한다.

  1) 이전 n이 만드는 경우의 수   : dp[i] = dp[i-2] * 3; (단, i >= 4 && i += 2)

  2) 특수 모양 만드는 경우의 수 :  dp[i] += dp[j] * 2 (단, j <= i -4 && j -= 2)

 

 

💥 유의사항

- dp 배열을 long형으로 선언해야 한다.

 

---

🔺 다른 풀이들

- 어랏 이 규칙은.... 내가 못 찾을 것 같다...

dp[n] = dp[n - 2] * 4 - dp[n - 4]

프로그래머스 JAVA Level2: 3XN 타일링

 

 

- 2중 for문을 만드는 대신 sum 변수를 활용하셨다.

public int tiling(int n) {
    if(n % 2 == 1){
      return 0;
    }
    
    int[] dp = new int [n + 1];
    dp[0] = 1;

    int sum = 0;
    for(int i = 2 ; i <= n ; i += 2){
         dp[i] = (dp[i - 2] * 3 + sum * 2) % 100000;
         sum += dp[i - 2];
    }

    return dp[n];
}

 

---

💬 느낀 점

특수 모양에서 우짜지.. 하고 점화식 여러개 해보다가 실패해서

다른 분들 코드 보고 참고했다..

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

프로그래머스(3xn 타일링, 가장 먼 노드) - Java

 

[프로그래머스 Level 4] 3 x n 타일링