76. C++ 백준 11726 번 2Xn 타일링 자세한 설명

안녕하세요 코딩하는 덕구입니다.

다이나믹 프로그래밍 문제인 C++ 백준 11726 번 2Xn 타일링 입니다.

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

백준 11726 C++ 정답 코드 입니다.

#include <iostream>
#define MAX 1001
using namespace std;
long long tiles[MAX] = {0, 1, 2,};
int cnt = 2;

int main(){
    int n;
    cin >> n;

    while ( cnt < n ){
        cnt++;
        tiles[cnt] = (tiles[cnt - 1] + tiles[cnt - 2]) % 10007;
    }

    cout << tiles[n];

    return 0;
}

 

먼저 타일을 2*n개의 직사각형에 배치하는 방법은 두 가지가 있습니다.

1) 1*2 타일을 넣는다

2) 2*2 타일을 넣는다.

왜 2*1 이 아닌 2*2 tile인지 궁금하실 텐데

어차피 2*1 타일을 위에 넣으면 아래에는 자동적으로 2*1 타일을 넣어야만 하기에

2*2타일이라고 생각해도 논리적으로 같습니다.

 

이제 2*n의 직사각형에 타일을 넣어봅시다.

 2*2의 직사각형에는 두 가지 방법이 있습니다.

1. 1*2 타일을 맨 뒤에 넣는다. | |

2. 2*2 타일을 맨 뒤에 넣는다. =

 

 2*3의 직사각형은 

2*3 직사각형에 맨 뒤에 2*1 타일이 들어가면

자연스럽게 남는 공간은 2*2 이 되므로  Base Case 2*2의 타일링 경우의 수를 더해주고 (n-1) 이미 저장되어 있음

 

2*3 직사각형에 맨 뒤에 2*2 타일이 들어가면

자연스럽게 남는 공간은 2*1 이 되므로 Base Case 2*1 의 타일링 경우의 수를  더해주면 (n-2) 이미 저장되어 있음

2*3직사각형의 타일링 경우의 수가 완성이 됩니다.

 

2*4의 직사각형은

2*4 직사각형에 맨 뒤에 2*1 타일이 들어가면

자연스럽게 남는 공간은 2*3 이 되므로  앞서 구한 2*3의 타일링 경우의 수를 더해주고 (n-1) 방금 구함

 

2*4 직사각형에 맨 뒤에 2*2 타일이 들어가면

자연스럽게 남는 공간은 2*2 이 되므로 Base Case 2*2 의 타일링 경우의 수를  더해주면 (n-2) 이미 저장되어 있음

 

즉 사전에 구한 (n-1) + (n-2) 의 타일링 경우의 수가 n 번째 타일링 경우의 수가 됩니다.

 

결국

(n-1) + (n-2) 을 더해서 n번을 구하는 코드입니다.

리스트인 tile 안에 0, 1, 2번은 Base Case로 넣었고

 

입력 값이 행렬 안에 있는지 검사한 후

만약 없다면

while ( cnt < n )

 

없는 부분을 계산해서 문제에서 요구한 저장 방식인 10007로 나눈 나머지 값을 넣어주었습니다.

while ( cnt < n ){
    cnt++;
    tiles[cnt] = (tiles[cnt - 1] + tiles[cnt - 2]) % 10007;
}

 

그리고 n번째 값을 출력하면 됩니다.

cout << tiles[n];

 

백준 11726 C++ 최종 코드 입니다.

#include <iostream>
#define MAX 1001
using namespace std;
long long tiles[MAX] = {0, 1, 2,};
int cnt = 2;

int main(){
    int n;
    cin >> n;

    while ( cnt < n ){
        cnt++;
        tiles[cnt] = (tiles[cnt - 1] + tiles[cnt - 2]) % 10007;
    }

    cout << tiles[n];

    return 0;
}

 

C++ 백준 11726 자세한 설명과 함께 정답 코드이었습니다.

 

감사합니다.