[프로그래머스][Level2][Java] 2xn 타일링

문제

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

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

 

풀이코드

우선 이 문제는 가로로 2개를 합친 덩어리를 1개로 취급하고,

세로로 2개를 합친 덩어리는 각각 1개씩 2개로 취급하고 풀었더니

예를 들어 주어진 n의 값이 7이면

7C0 + 6C1 + 5C2 + 4C3 => 답

이런 공식이 나왔었다.

그래서 처음의 풀이코드는 이러한 조합을 이용해서 풀려고 했다.

public int solution(int n) {
    int answer = 0;
    for(int i = 0;i < n;i++){
        if(n-i<i){
            break;
        }
        answer += combination(n-i,i);
    }
    return answer;
}
static int[][] combi;
public int combination(int a, int b) {
    if(a == b || b == 0){
        return combi[a][b] = 1;
    }else{
        return combi[a][b] = (combination(a-1,b-1)+combination(a-1,b))%1000000007;
    }
}

하지만 계속 NullPointerException 오류가 났고 코드를 천천히 살펴보니 solution메서드의 answer은 int형인데

combination의 메서드는 return 값이 배열이라서 오류가 난 것이었다.

그렇다고 그냥 조합메서드를 따로 만들어서 풀었더니 이건 또 조합공식을 적용하는 도중에 숫자가 너무 커져서 오류가 나서 실패를 했다. 그래서 다른 방법이 없나 싶어서 n에 따른 결과값들을 쭉보니 피보나치 수열과 같은 결과가 나와서

public int solution(int n) {
    int[] com = new int[n+1];   // 입력한 길이보다 1많게 배열 생성
    com[1] = 1;                 // 길이가 1일때, 경우의 수
    com[2] = 2;                 // 길이가 2일때, 경우의 수
    for(int i = 3; i <=n ;i++){ // 길이가 3이상일 때, 경우의 수
        com[i] = (com[i-1]+com[i-2])%1000000007;
    }
    return com[n];
}

이렇게 피보나치를 응용해서 풀었는데 왜 이런 결과가 나오는지 의아해서 곰곰히 생각을 해봤다.

우선 세로의 길이가 2로 고정이니 가로의 길이가 1과 2로 변하는 것만 생각해서 풀어주면 되는데,

n = 1 -> (1)

n = 2 -> (1+1) , (2)

n = 3 -> (1+1+1), (1+2), (2+1) -> 편의상 n = 3일때 수들을 초록색으로 표시하겠음

n = 4 -> (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2)

여기에서 볼 수 있듯이 n - 1번째에 나왔던 경우의 수에 가로가 1일때를 더한 것과

n - 2번째에 나왔던 경우의 수에 가로가 2일때를 더한 모든 경우의 수가 n번째 경우의 수가 된다.

그래서 com[n] = com[n-1] + com[n-2]가 되는 것이다.

 

사실 왜 피보나치로 나오는지 이유를 찾으려고 검색을 해봤지만 다들 그냥 일일히 계산하면 피보나치였다! 라고

해서 조금 답답해서 직접 생각을 해봤더니 저런 이유였다! 그림으로 저것을 그려보면 보다 이해하기가 쉬울 것이다.