[BaekJoon 11726번] 2xn 타일링(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

11726번: 2×n 타일링

 

 

[문제 설명]

 

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

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

 

 

 

[입력]

 

 

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

 

 

[출력]

 

 

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

 

 

[입출력 예]

 

입력	출력
2	2
9	55

 

 

[문제 풀이]

 

쉬웠던 문제..

점화식을 얻기 위해 노트에 그려가면서 풀었다.

 

끄적 끄적

이렇게 끄적이다보니 눈에 보이는게 있었다. 피보나치 수열의 점화식이 눈에 보였다.

n - 1 일 때는 (2x1 1개)n - 2  일 때는 (2x1 2개 또는 1x2 2개)

n 타일링 방법의 수 =  n-1 타일링 방법의 수 + n-2 타일링 방법의 수 라는 것을 말이다.

 

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

라는 문구가 있다.

 

이렇게 주어지는 이유는 결과값이 너무 크기때문에 오버플로우를 방지하고자

문제에서 친절하게 모듈러 연산(나머지 연산)을 하라고 주어진다.

 

보통 이렇게 주어지면 단순히 결과 값에 모듈러 연산을 수행하는 것이 아니라

연산 과정 도중에 모듈러 연산을 수행해야 한다.

 

[알고리즘] 모듈러 연산(나머지 연산)

 

 

[최종 코드]

 

 

[GitHub]

 

 

(Top - Down)

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

(Bottom - Up)

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

(Top - Down)

#include <bits/stdc++.h>
using namespace std;
#define MAX 10007

int n;
int save[1001];

int tiling(int n) {
    if (save[n] != 0) return (save[n]) % MAX;
    else {
        return save[n] = (tiling(n-1) + tiling(n-2)) % MAX;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n; // 입력
    save[1] = 1;
    save[2] = 2;
    cout << tiling(n);
}

 

(Bottom - Up)

#include <bits/stdc++.h>
using namespace std;
#define MAX 10007

int n;
int save[1001];

int tiling(int n) {
    for(int i = 3; i <=n; ++i) {
        save[i] = (save[i-1] + save[i-2]) % MAX;
    }

    return save[n] % MAX;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n; // 입력
    save[1] = 1;
    save[2] = 2;
    cout << tiling(n);
}