M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 11727 - 2*n 타일링2

최대 1 분 소요

문제

백준 11727 - 2*n 타일링2 풀러가기

문제 분석

이 문제는

  • 작은 문제로 나눌 수 있고
  • 작은 문제가 중복되며, 작은 문제의 답은 항상 같다.

따라서, 다이나믹 프로그래밍 으로 풀 수 있다.

2*n이 주어졌을 때,

제일 오른쪽에 넣을 수 있는 사각형의 종류는 1 by 2, 2 by 2, 2 by 1이 있고.

  • 제일 오른쪽에 1 by 2가 들어가는 경우는 d[n-1]을
  • 제일 오른쪽에 2 by 2 가 들어가는 경우는 d[n-2]를
  • 제일 오른쪽에 2 by 1 가 들어가는 경우는 d[n-2]를

생각 할 수 있다.

따라서 d[n] = 2*d[n-2] + d[n-1] 의 점화식을 만들 수 있고, 이를 코드로 구현하면 된다.

문제 풀이(C++)

  1. 전체 코드(TOP-DOWN 방식)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    #include <cstdio>
     
    using namespace std;
     
    int d[1001];
     
    int way(int n) {
        if (d[n] > 0) {
            return d[n];
        }
     
        d[n] = (way(n - 1) + (way(n - 2) * 2)) % 10007;
     
        return d[n];
    }
     
    int main() {
     
        int n;
     
        scanf("%d", &n);
     
        d[0] = 1;
        d[1] = 1;
     
        way(n);
     
        printf("%d", d[n]);
     
        return 0;
    }
    		cs





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고