[백준] 11726. 2*n 타일링

문제

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



풀이

생각보다 고민을 많이 했던 문제이다. 다이나믹 프로그래밍으로 풀 수 있는 문제이다. 보통 다이나믹 프로그래밍은 점화식을 어떻게 세우느냐를 잘 생각해야 하는데, 한 번 어긋나기 시작하면 끊임없이 틀리게 된다. 자신이 생각하고 있는 풀이가 뭔가 답이 안나온다면 주저없이 다른 방법을 생각해보자.

2*n 타일링이므로 가능한 건 세로 모양이나 가로 모양 2개를 쌓은 모양이 될 수 있다. 이걸 잘 생각해서 풀어보자.

2 * 1 일 때

2 * 2 일 때

  

2 * 3 일 때 : 길이가 3일 때부터 점화식이 적용되기 시작한다. 2 * 1에 가로 두 개짜리를 붙인 모양 (1 번째 그림) 과 2 * 2에 각각 세로 1개 짜리를 붙인 모양 (2 ~ 3 번째 그림)이 2 * 3 타일링이 된다.

    

2 * 4 일 떄 : 길이가 4인 경우도 마찬가지로 2 * 2에 가로 두 개짜리를 붙인 모양 (1 ~ 2 번째 그림) 과 2 * 3에 각각 세로 1개 짜리를 붙인 모양 (3 ~ 5 번째 그림)이 2 * 4 타일링이 된다.

        

이 과정을 통해 아래와 같은 점화식이 나온다는 것을 알 수 있다.

    dp[i] = dp[i - 2] + dp[i - 1]

소스코드

//
//  2byNTiling.cpp
//  test
//
//  Created by 신기열 on 27/05/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int main(){
    
    int tile[1001], n;
    cin >> n;
   
    tile[1] = 1; tile[2] = 2; tile[3] = 3;
    
    for(int i = 4; i < 1001; i++){
        tile[i] = (tile[i - 1] + tile[i - 2]) % 10007;
    }
    
    cout << tile[n] % 10007;
    
    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/DP/2byNTiling.cpp




++
문제에서 10007로 나눈 나머지로 구하라고 명시되어 있다. 여기서 n까지 구한 값에 10007을 나눈게 답일 것 같지만, 왜 모든 배열값에 10007로 전부 나눠줬는가 하면, 연산을 하는 도중 자료형이 담을 수 있는 범위, 가령 몇십억이 된다면 오버플로우가 되버린다. 그래서 처음부터 10007로 계속 나눠준 것이다.

그렇다면 출력 부분에 있는 10007 연산을 없애준다면? 상관없다. 10007로 나눈 값이나 10007로 나눈 값을 10007로 나눈 값의 나머지나 같다는 것은 기초적인 연산만 해봐도 알 수 있는 부분이며, 저렇게 해준 이유는 단지 문제에서 요구한게 마지막에 도출 된 값에 10007로 나눈 나머지를 구하는 것이기 때문에 한번 더 나누어줬을 뿐, 큰 의미는 없다.