# 프로그래머스 : 2 x n 타일링 (Level 5)

[문제]

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

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

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

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

[풀이]

드디어 내 힘으로 DP를 이용하여 풀었다! (엄청난 감동이 밀려옴)
우선 이 문제는 그림으로 직접 그려보면 피보나치 수열처럼 규칙이 존재한다는 것을 볼 수 있다.

나는 직접 1부터 6까지 그려보았는데,

1과 2일때는 문제에서 제공하고 있기 때문에 패스하였다.
이를 통해, dp[n]이 n개의 타일에서 만들 수 있는 답의 갯수 라고 할 때
dp[n] = dp[n-2] + dp[n-1]이 된다.

물론! 피보나치로도 풀 수 있었지만, 오늘 DP를 공부했으니 한번 이용해보자.

int tiling(int n)

{

    int answer = 0;

    vector<int> dp(n, 0);

    int index = 1;

    dp[0] = 1;

    dp[1] = 2;

    if(dp[n-1] == 0) {

        for(int i=2; i<n; i++) {

            dp[i] = dp[i-1] + dp[i-2];

            if(dp[i] > 100000) {

                dp[i] %= 100000;

            }

        }

    }

    return dp[n-1] % 100000;

}

dp[0]과 dp[1]일 때 각각 갯수를 미리 넣어주고, 마지막 dp[n-1]까지 값을 계산한다.

문제에서 조금 헷갈리는 부분이 있었는데, 5자리가 넘어가면 5자리만 출력해서 반환하라고 하였다.

이게 답에서만 그러는 것이 아니고, dp[i]가 5자리가 넘어가도 5자리만 출력하라는 말이었다.

(이걸 정확하게 이해하지 못해서 시간을 좀 낭비했다는..)

마지막 답변이 만약 5자리가 넘더라도 5자리만 출력해달라는 '까다로운 요구' 덕분에

각각에 조건부에 따른 %100000을 해서 마지막 5자리만 출력할 수 있도록 하였다.

Level 5 치고는 굉장히 금방 풀어버린 문제!

내 실력이 늘었기 때문 이었으면 좋겠다.