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

https://programmers.co.kr/learn/courses/30/lessons/12900

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

 

[ 풀이 ] 

 

 

문제에서 예시로 나온 n = 4 의 경우를 보자. 총 가능한 경우의 수는 다음과 같다.

• 1  1  1  1
• 1  2  1 
• 2  1  1 
• 1  1  2 
• 2  2

여기서 파란색 부분과 빨간색 부분을 보자. 파란색 부분은 n = 3 일 때의 총 가능한 경우의 수이며, 빨간색 부분은 n = 2 일때 총 가능한 경우의 수이다. 

파란색 부분을 떼어서 다시 분석해보자.

• 1  1  1  
• 2  1  
• 1  2

마찬가지로 빨간색 부분은 n = 2 일 때 총 가능한 경우의 수이며 , 초록색 부분은 n = 1 일때 가능한 경우의 수이다.

 

위 규칙을 통해서 알 수 있는 것은 n 에 대한 총 가능한 경우의 수 f( n ) 에 대하여 다음과 같은 식이 성립한다.

f( n ) = f( n -1 ) + f( n - 2 )

그래서 곧 바로 재귀를 이용해서 풀어보았다. 이 때 문제에서 1000000007 로 나눈 나머지를 구하라고 하였으므로 재귀를 반복할 때 마다 1000000007 로 나눈 나머지를 리턴한다.

 

class Solution {    
    public int solution(int n) {
        int answer = tile( n ) % 1000000007;               
        return answer;
    }
    static int tile( int n ){
        if( n == 1 ) return 1 ;
        if( n == 2 ) return 2 ;
        return ( tile( n - 1 ) + tile( n - 2 ) ) % 1000000007;
    }
}

예제 케이스는 통과하였으나 테스트 케이스 모두 시간초과가 발생하였다. 

 

이번에는 DP를 이용해서 시도해보았다.

 

[ 전체 코드 ]

class Solution {    
    public int solution(int n) {
        int[] tile = new int[n];
        tile[0] = 1;
        tile[1] = 2;
        for( int i = 2 ; i < n ; i++ ){
            tile[i] = ( tile[ i - 2 ] + tile[ i - 1 ] ) % 1000000007;
        }
        int answer = tile[n - 1];               
        return answer;
    }
}

 

결과는 정확성 테스트, 효율성 테스트 모두 통과하였다.