2xn 타일링

1x1 정사각형 2개가 붙어 있는 타일이 있습니다. 이 타일을 이용하여 총 2xN 의 보드판을 채우려고 합니다. 타일은 가로, 세로 두 가지 방향으로 배치할 수 있습니다.

보드판의 길이 N이 주어질 때, 2xN을 타일로 채울 수 있는 경우의 수를 반환하는 tiling 함수를 완성하세요.

예를들어 N이 7일 경우 아래 그림이 타일을 배치할 수 있는 한 경우입니다.

단, 리턴하는 숫자가 매우 커질 수도 있으므로 숫자가 5자리를 넘어간다면 맨 끝자리 5자리만 리턴하세요.예를 들어 N = 2일 경우 가로로 배치하는 경우와 세로로 배치하는 경우가 있을 수 있으므로 2를 반환해 주면 됩니다. 하지만 만약 답이 123456789라면 56789만 반환해주면 됩니다. 리턴하는 숫자의 앞자리가 0일 경우 0을 제외한 숫자를 리턴하세요. 리턴타입은 정수형이어야 합니다.

강의에서도 나왔던 문제였고, 쉽게 생각했었는데 직접 푸니까 이상한데서 막혔다. 바로 n-2번째 개수에 세로 두개, 가로 두개를 붙이는 경우를 모두 생각해버린것. 이렇게 되면 n-1번째 개수에 세로 한개를 세우는 것과 경우가 겹쳐서 제대로 값을 구할 수 없다. n-1에서는 세로 한개, n-2에서는 가로 두개만 생각해줘야한다. 그렇게 하면 피보나치와 같은 점화식이 만들어지고, 금방 답을 얻을 수 있다. 여담으로 return을 하는 과정에서 나머지 연산을 해주는 것이 아니라 배열에 값을 집어넣을때 해줘야 틀리지 않는다.

class NTiling {
    public int tiling(int n) {
        int answer = 0;
        int d[] = new int[n];
        d[0] = 1;
        d[1] = 2;
        
        for(int i = 2; i < n;i++) {
            d[i] = (d[i-1] + d[i-2])%100000;
        }
        answer = d[n-1];
        return answer;
    }
 
    public static void main(String args[]) {
        NTiling tryHelloWorld = new NTiling();
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.print(tryHelloWorld.tiling(2));
    }
}