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

연습문제 3xn타일링

이 문제를 풀면서 프로그래머스에서는 static변수는 정말 유용하지 않구나를 깨달았다. 다른 swea나 백준을 풀때처럼 

static변수에 5000까지를 모두 계산해서 넣어둘 생각을 하였는데, 음.. 매번 새로 class를 생성하는지 static의 의미가 전혀 없이 모두 시간초과 가 발생하였다..

그래서 불러올때마다 계산하는 방법으로 코딩하니  통과...마음이 아프다... 나는 무엇을 위해 효율성을 생각했는가.

그림 그려서 차근차근 푸니 

f(n) = 3*f(n-2) + 2*f(n-4) + .....+ 2*f(2) +2 라고 생각하면 된다..

아래는 문제 설명이다..

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

nresult

4

11

입출력 예 설명

입출력 예 #1
다음과 같이 11가지 방법이 있다.

 

 

 

 

 

 

 

 

 

 

 

아래는 풀이한 코드가 된다. 사이즈가 크니. long 배열로 선언해서 해결하면 된다. 

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

아무 문제 없는 쉬운문제.. 허허허허허 mod를 조심하고, static을 조심하자...