문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

어떻게 풀 것인가?

과정을 생략하고 코드를 보고싶은 분은 맨 아래로

접근 방법 : Dynamic Programming

보자마자 생각했다. Dynamic Programming.
2 n 의 타일을 만드는 갯수는 2 (n-1) 또는 2 * (n-2)의 갯수와 관계가 있을것이 분명하다!
이 관계를 찾아야 한다.

기본 입출력 정의

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin>>t;
    int dp[t+1];

		dp[1] = 1;
		dp[2] = 2;

}

t를 입력받아 dp배열을 생성하고 dp[1] = 1, dp[2] = 2로 초기화 한다.

💢 타일이 중복과 추가가 되는구나💢

처음에는 n번째 타일의 양쪽에 세로 타일을 붙이는 것을 생각했다.

근데 중복되는 타일과 추가되는 타일이 생긴다. 중복되는 타일과 추가되는 타일에 대한 규칙을 찾기 어려웠다...
타일을 양쪽에 붙인다는 규칙으로는 규칙성이 생기지 않는 것 같다. → 타일을 한방향(오른쪽)으로 붙이자!

한방향으로 타일 붙이기

그러면 한방향으로 타일을 2개(세로+세로 / 가로 + 가로)를 붙일 것인지? 혹은 타일을 1개를 붙일 것인지 생각해야 했다.

n번째 타일은 n-2번째 타일에서 (세로+세로)타일을 붙이거나 (가로+가로)타일을 붙이는 것이다.
➕
n번째 타일은 n-1번째 타일에서 (세로) 타일을 붙이는 것이다.

그림에서 보이는 것 처럼 중복이 발생한다.

중복은 어떻게 이루어지나?

중복이 되는 타일만 제거를 하면 될 것 같다.
중복이 어떻게 생기는지 알아보기 위해서 다 그려봤다.

그리다 보니 드는 생각
세로 타일로 끝나는 타일만 ➕ 맨 오른쪽 세로타일이 2개 이상인 타일
만 중복이 일어난다!

💥 결론 : n-2번째에서 세로타일을 두개 붙이는 타일은 중복이 일어난다!

그렇다.
그럼 dp식을 완성해보자.
dp[n] = dp[n-2] * 2 (n-2 타일에 세로 + 세로, 가로 + 가로 붙이기)
➕ dp[n-1] (n-1 타일에 세로 붙이기)
➖ dp[n-2] (n-2 타일에 세로 + 세로를 붙이는 건 중복된다.)

dp[n] = dp[n-2] + dp[n-1]

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin>>t;
    int dp[t+1];

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3;i<t+1;i++){
        dp[i] = dp[i-2] + dp[i-1];
    }

    cout<<dp[t];
}

예제입력은 잘 돌아간다.
하지만 섣부르게 제출하면 바로 틀립니다.....
😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭

네 그렇습니다. 어쩐지 바로 그냥 틀려버리더라

바로 틀린다 → 큰 수의 입력에서 틀린다!

제출하기 전에 Check할 것!

1. 입력, 계산, 출력값이 int의 자료를 넘어가는가? (int = 2,147,483,648)
2. 작은 값의 입력을 잘 해결하는가? (1, 2 정도의 입력을 해보자)
3. 불필요한 log들 전부 지우고 제출해봅시.
4. ➕ 문제에서 추가로 요구하는 요구사항은 없는가?

코드를 수정해준다.

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin>>t;
    int dp[t+1];

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3;i<t+1;i++){
        dp[i] = (dp[i-2] + dp[i-1]) % 10007;
//        dp[i] = dp[i-2] + dp[i-1];
    }

    cout<<dp[t];
}

👨‍💻 재도전! 🚙

---

과 함께 성공했습니다 :)

🌕 FULL CODE ⛽

---

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin>>t;
    int dp[t+1];

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3;i<t+1;i++){
        dp[i] = (dp[i-2] + dp[i-1]) % 10007;
//        dp[i] = dp[i-2] + dp[i-1];
    }

    cout<<dp[t];
}

🤜 FeedBack 🤛

---

1. 채점 시간이 엄청 오래 걸리던데 왜그런걸까..?
2. 문제 제대로 읽자 ^^......ㅜㅜㅜㅜㅜ