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

※주의※

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

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

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

 

 

[문제 풀이 사이트]

 

 

11727번: 2×n 타일링 2

 

 

[문제 설명]

 

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

 

 

[입력]

 

 

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

 

 

[출력]

 

 

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

 

 

[입출력 예]

 

 

입력	출력
2	3
8	171
12	2731

 

 

[문제 풀이]

 

 

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

이문제는 11726번 2xn 타일링과 매우 유사한 문제이다.

그래서 똑같이 노트에 끄적이며 점화식을 도출하려했다.

 

 

끄적이다보니 점화식을 찾았다.

n-1일 때는 경우의 수 1 (2x1 타일)

n-2일때는 경우의 수 2 (2x2타일, 1x2 or 2x1 타일)

점화식 : n 타일링 방법의 수 = n-1 타일링 방법의 수 + (2 x (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 save[1001];

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    save[1] = 1;
    save[2] = 3;
    cout << tiling(n);
    return 0;
}

 

(Bottom - Up)

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

#define MAX 10007
int save[1001];

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    save[1] = 1;
    save[2] = 3;
    cout << tiling(n);
    return 0;
}