[알고리즘] 백준 11726번 2*n 타일링 문제 DP

안녕하세요, 감자코딩에 감자개발자입니다.

대학생분들은 중간고사 시즌이실텐데요. 저 또한 그렇지만 이번에 중간고사 시험을 하나만 치르게됩니다 : ) 

이번에 살펴볼 알고리즘 문제는 백준알고리즘 11726번 2*n 타일링 문제입니다.

저번에 살펴봤던 문제는 1로 만들기 문제였었는데요, 이번엔 재미가 아주 있는 타일링 문제입니다. DP적인 사고를 만들기에 충분한 문제인데요.

바로 들어가겠습니다 :)

1. 문제

2×n 타일링 성공

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초 256 MB 35997 13221 9954 34.803%

문제

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

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

입력

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

출력

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

예제 입력 1 

2

예제 출력 1 

2

예제 입력 2 

9

예제 출력 2 

55

네, 이번에는 전형적인 DP 문제 입니다. 타일링 문제를 읽어보시면서 각각의 경우를 구해보셨을텐데요. 이때, DP 문제라고 생각하셨던 부분이 어디셨나요? 만약 생각하지 못하셨어도 괜찮습니다. 이제부터 하면 됩니다. 제가 차근차근 알려드리겠습니다.

2. 문제 해결 방법

1) 키워드: 2*n의 직사각형, 1*2, 2*1타일, 채우는 방법의수를 10007로 나눈 나머지 출력, 1 ≤ n ≤ 1,000

키워드를 살펴보시면 딱 문제의 요약이라고 할 수 있는데요. 

일단 N의 개수를 입력받아 우리가 원하는 2*N의 직사각형에서 1*2와 2*1타일을 가지고 타일을 채우는 방법의 수를 찾는 문제입니다. 

저는 TOP-DOWN방식을 사용할것이므로, 직사각형의 맨 오른쪽에서 부터 시작하겠습니다. 결국 높은곳에서 Recursive를 통한 아래의 값까지 접근하겠다는 말이겠죠? 

혹시 이 말이 이해가 안가신다면, 제가 전 강의에 잘 정리해놓은 글을 읽어보시면 되겠습니다. 

[왼쪽 그림]

왼쪽그림은 2*n 타일에 1*2의 타일을 가지고 만드는 방법의 수를 나타낸 그림입니다.

전체 가로의 길이 N길이의 타일의 길이에서 1*2타일로 만드는 경우의 수를 점화식으로 나타내면 2 * (N-2)가 됩니다. 

[오른쪽 그림]

오른쪽 2*n 타일에 2*1의 타일을 가지고 만드는 방법의 수를 나타낸 그림입니다.

전체 가로의 길이 N길이의 타일의 길이에서 2*1타일로 만드는 경우의 수를 점화식으로 나타내면 2 * (N-1)가 됩니다. 

어떤가요? DP 감이 잡히시나요? 직접 반드시 그려보시길 바랍니다!

그러면 이걸 DP로 적용한다면 어떻게 될까요?

DP = recursive(n-2) + recursive(n-1) 

2*1을 타일의 경우의 수와 1*2의 타일의 수를 구하게 된다면 최종적으로 모든 타일의 경우의 수를 구할 수 있겠죠? 

네, 그러면 바로 코드를 보면서 이해해보시면 되겠습니다.

2) 시간복잡도 

네, 이번에는 시간복잡도에 대해서도 살펴볼것입니다.

n의 범위는 1<= n <= 1000까지라고 정의되어있겠죠?

만약 O(n) 의 범위 일경우에는 1000까지의 시간복잡도가 만들어지게 되겠습니다.

컴퓨팅 시간복잡도 연산에 있어서는 1초에 1억번이라는것 무조건 기억하셔야합니다.

그러면, O(n^2)의 시간복잡도는 어떻게 될까요?

네, 그렇습니다. 1,000,000(=백만) 이 됩니다.  

하지만, 우리가 이번에 구현한 DP 알고리즘은 시간복잡도가 O(NlogN)이 될것입니다.

왜 그럴까요? 

재귀호출을 이용하면서 호출 횟수가 

2^n -> 2^n-1 -> 2^n-2.... 2^1까지 분기를 하면서 재귀호출을 하게될텐데요.

이때 연산의 횟수는 2^0 -> 2^1 -> .... 2^n까지 연산을 하게 되겠습니다.

또, 2^n -> 2^n-2-> 2^n-4.... 2^1까지의 시간복잡도도 이해해주셔야합니다.

하지만, 시간복잡도에 영향을 끼치지는 않습니다. 왜냐하면, O(logN) + O(logN)이 되겠지만, 결국엔 앞에 상수는 무시하게 되겠습니다. 따라서 결국 O(logN)의 시간복잡도만 생각해주면 되죠.

그리고 구하고자하는 2*N타일의 N의 값까지 호출을 하게하므로 데이터의 개수인 O(N)까지의 데이터를 호출을 진행합니다.

결국 시간복잡도는 O(NlogN)의 복잡도를 가지게 된답니다.

한번 잘 유념하시고 확인해보시길 바랍니다. :)

3. 코드 리뷰

//

//  2*n타일링.cpp

//  beakjoon_algorithm

//

//  Created by kgh on 12/04/2019.

//  Copyright © 2019 kgh. All rights reserved.

//

#include <stdio.h>

#include <iostream>

using namespace std;

int dp[1001];

int recursive(int n){

    

//N이 1일경우

    if(n == 1){

        return 1;

    }

//N이 2일경우 (1*2, 2*1)의 두가지 경우이므로

    if(n == 2){

        return 2;

    }

//이미 타일을 만들었던 경우의 수라면 기존값 리턴

    if(dp[n] > 0){

        return dp[n];

    }

// DP값에 10007을 나눈 나머지를 구하라고 하였죠.

    dp[n] = (recursive(n-1) + recursive(n-2)) % 10007 ;

    return dp[n];

    

    

    

}

int main(void){

    int n;

    cin >> n;

    int result = recursive(n);

    

    cout << result ;

    

    return 0;

}

대표적인 DP문제인 2*N 타일링 문제에 접근해 보았습니다.

차근차근 하나씩 풀어보시다보면 감이 잡힐 것이라고 믿습니다.

이상 감자코딩에 감자개발자였습니다.

잘못된 부분이 있다면 댓글을 남겨주세요. 피드백은 사랑입니다