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

 

문제분석

 

문제는 아주 심플하다.  가로 2 세로 1인 블록을  3XN타일에 몇개까지 완벽하게 가득 넣을수 있는지 묻는다.

 

문제 읽자마자  떠오르는게 '규칙찾기' 이다.

 

혹여나, 규칙을 찾으신분은  별탈 없이 이문제는 프리패스지만..  못찾는게 대부분이다.

 

규칙을 찾기위해선 먼저 증거들을 수집해 보자.

 

n=0 , 1

n=2 , 3

n=4 , 11

 

-> 홀수를 빼먹엇는데 홀수의 경우수는 완벽하게 가득 넣을수없으니 0개다.

 

저 3가지의 경우를 보고 규칙이 보이는가?  대부분 못찾는다..

 

n=6일땐 경우의수가 41이나온다.  n=6인 예시도 있었다면 규칙을 쉽게찾앗겟지만 주지않는다.

만약 실제 코딩테스트문제라면 빠른 구글링을하자.,, 괜히 규칙찾는다고 시간낭비다.

 

필자도 고민해보다 구글링을 했는데, 

규칙은 f(n)= f(n-2)*4 - f(n-4) 가 나온다.

 

이 하향식 규칙을 사용하려면 모듈러 분배규칙을 사용해야한다.

class Solution {
    long[] tile = new long[5001];
    
    public long solution(int n) {
        long answer = 0;
        int mod=1000000007;
        //1:2, 2:3, 3:6 4:11
        // 규칙활용 f(n) = f(n-2)*4 - f(n-4)
        tile[0]=1;
        tile[2]=3;
        
        //f(n) = ((f(n - 2) x 4 % 1,000,000,007) 
        //- (f(n - 4) % 1,000,000,007) + 1,000,000,007) % 1,000,000,007
       for(int i=4; i<=n; i+=2){
           tile[i]= (tile[i-2]*4%mod -tile[i-4]%mod +mod)%mod;
        
        };
        
        return answer=tile[n];
    }
    
  
}

이 코드도 잘 동작한다.

 

 

 

 

또다른 규칙은 이런 규칙도있다.

 dp[i] = dp[i-2] * 3 (i>=4, 2씩 증가)

 dp[i] += dp[j] * 2 (j <= i-4, 2씩 차감) 이다.

 

 

만약 규칙이 구해지는 과정을 보고싶다면 아래 블로그에서 설명을 잘해준다.

 

https://s2choco.tistory.com/24

프로그래머스 - 3xn 타일링 풀이 (python3)

 

규칙을 알앗다면 바로 적용해보자!

 

문제풀이

class Solution {
    long[] tile = new long[5001];
    
    public long solution(int n) {
        long answer = 0;
        int mod=1000000007;
  
        tile[0]=1;
        tile[2]=3;
        
       for(int i=4; i<=n; i+=2){
            tile[i] = tile[i-2] * 3;
            for(int j=i-4; j>=0; j-=2){
                tile[i] += tile[j] * 2;
            }
            tile[i] = tile[i] % mod;
        };
        
        return answer=tile[n];
    }
    
  
}