알고리즘 :: 백준 :: DP :: 11727 :: 2xn 타일링2

Embedded June·2020년 7월 20일
0

알고리즘::백준

목록 보기
5/109
post-thumbnail

문제

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

문제 접근

가로의 길이가 n이므로 놓는 타일이 무엇이냐에 따라 다음 작은 문제는 n-1또는 n-2일 것이다.

  • 임의의 숫자 n에 대해 경우의 수를 기록해둔다면 중복 연산을 피할 수 있으므로 DP 방법이 유효하다.
  • 2×n2\times n 타일을 만드는 경우의 수는 우측 맨 끝에 1×21\times 2 타일을 2개 놓았을 때와 2×12\times 1 타일을 1개 놓았을 경우 그리고 2×22\times 2타일을 1개 놓았을 때로 나눌 수 있다.
  • 1×21\times 2 타일을 2개 놓았을 때와 2×12\times 1 타일을 1개 놓았을 경우는 동일하다는 것을 아는 것이 핵심이다.
  • 따라서 점화식은 D(n)=D(n1)+2D(n2)D(n) = D(n-1) + 2D(n-2)이다.

코드

#include <iostream>
#include <cstring>
using namespace std;

static int n = 0;
static int cache[1001];
int solve(int num) {
    if (num == 0 || num == 1) return 1;
    if (cache[num] > 0) return cache[num];
	// 2xn 타일을 만드는 경우의 수는 (1x2 2개 또는 2x2 1개) + (2x1 2개)이다.
    return cache[num] = (solve(num - 1) + 2 * solve(num - 2)) % 10007;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    memset(cache, 0, sizeof(cache));
    cout << solve(n) << '\n';
}

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글