[알고리즘] 백준 11727 2*n 타일링 2 DP

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

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

저번에 2*n 타일링문제를 잘 풀어보셨다면, 이 문제 또한 수월하게 푸실 수 있을것입니다.

문제부터 살펴보죠.

문제 링크

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

1. 문제

2×n 타일링 2 성공

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

1 초 256 MB 15559 9176 7458 59.436%

문제

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

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

입력

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

출력

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

 

예제 입력 1 

2

예제 출력 1 

3

예제 입력 2 

8

예제 출력 2 

171

예제 입력 3 

12

예제 출력 3 

2731

2. 문제 해결 방법

1)  2*N 타일링을 만들어 2*1 , 2*1 ,2*2 타일링으로 채워나가는 경우의 수를 찾는 문제입니다.

2) 각각의 2*1 타일 , 2*1 타일, 2*2 타일에 경우의 수를 찾아보도록 하죠.

아래의 그림을 보시면 이해가 빠르실 것입니다.

(왼쪽), (가운데), (오른쪽)순으로 살펴보겠습니다.

DP = 2*N 이라는 사실과 최소의 도형의 개수를 생각하여야 합니다.

(왼쪽의 경우)

2*2 타일로 한번 채운 경우입니다.

(가운데의 경우)

1*2 타일로 두번 채운 경우입니다.

여기서 왜 두개를 채우냐고 생각하시는분이 있으실텐데 정확하게 n-2개만큼 처리해주기 위함입니다.

(오른쪽의 경우)

2*1 타일로 한번 채운경우입니다. 

그러면 이제, 총 3개의 타일을 이용하여서 2*N타일의 경우의 수를 찾아내면 되겠지요?

즉, 위의 그림을 보게 되면 왼쪽과 가운데의 점화식은 N-2가 되게 되는데 동일하다는 것을 발견하셨죠? 그러면 결국 2 * (N - 2)개의 경우의 수를 따져주게 되면 된답니다.

그리고, 오른쪽의 점화식은 N-1이 성립하는것을 알 수 있습니다.

이것을 DP로 문제를 풀게 된다면 이전의 2*N타일링 문제와 거의 유사한 문제가 되겠죠?

하지만 주의할 것은, N의 값이 1일 경우와 N의 값이 2일 경우에 리턴받는값이 달라진다는것 입니다. 

이것이 무슨 말인지 이해가 안가시는분도 있을겁니다.

- N = 1일 경우

2 * 1 의 타일링

- N = 2일 경우

2*2의 타일링

이 생성 됩니다. 그러면 우리가 가진 타일링의 종류는 총 3가지죠(2*1 ,2*1, 2*2) 타일입니다.

따라서, N=1 일 경우 총 2*1의 타일의 경우의 수 1개만 존재하게 되겠죠?

그리고 N=2 일 경우 총 (2*1, 1*2, 2*2) 타일이 존재 하므로, 총 3가지 경우를 리턴해주면 됩니다.

(2*1)

(1*2)

(2*2)

이해가 가시나요? 그러면 이제 소스코드를 작성해봅시다.

이해가 안가시는 분들은 

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

https://kgh940525.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-11726%EB%B2%88-2n-%ED%83%80%EC%9D%BC%EB%A7%81-%EB%AC%B8%EC%A0%9C-DP

여기를 참고하시고 오시면 되겠습니다.

3. 코드 리뷰

//

//  2*n타일링2.cpp

//  beakjoon_algorithm

//

//  Created by kgh on 13/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 한가지 경우 2*1

    if(n == 1){

        return 1;

    }

    // N == 2 1*2 , 2*1 , 2*2 3가지 경우 리턴

    if(n == 2){

        return 3;

    }

    // 값 존재시 dp[n] 리턴 메모이 제이션

    if(dp[n] > 0){

        return dp[n];

    }

    // 아까 구한 점화식 적용

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

    return dp[n];

}

int main(void){

    int n;

    cin >> n;

    

    // 최종 경우의 수 출력

    int result = recursive(n);

    cout << result;

    

    return 0;

    

}

2*N타일링 1 문제에 이어서 2*N타일링2 문제 까지 살펴보게되었습니다.

알고리즘을 평소에 많이 해놓으셔야지 저 처럼 인턴 시기에 힘들지 않습니다 D:

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

잘못된 부분이 있다면 의견 남겨주시면 감사하겠습니다 :)