Programmers - 2 x n 타일링

---

title: Programmers - 2 x n 타일링
date: 2022-06-21
tags:

• Algorithm
• DP

---

https://programmers.co.kr/learn/courses/30/lessons/12900

문제 요약

1x2 타일을 2xn 공간에 배치하는 모든 경우의 수를 구한다.

문제 풀이

전형적인 DP 입문 문제이다. n >= 3 일때, n번째 경우의 수는 n-2번째의 배치에서 가로로 배치하는 경우의 수와 n-1번째의 배치에서 세로로 배치하는 경우의 수의 합이다.
이전 두 단계의 값만 참조하기 때문에 과한 메모리를 할당할 필요 없이 길이 3의 배열만 있으면 된다.
n <= 3일 때는 연산 없이 바로 저장한 값을 return하고, n > 3 일 때 (n-3)번 DP 계산을 해준다. 계산 이후 배열의 마지막 element의 값이 정답이다.

프로그램

#include <string>
#include <vector>

using std :: vector ;
using std :: string ;

int solution ( int n )
{
    int irgDP [ 3 ] = { 1 , 2 , 3 } ;



    if ( n <= 3 )
        return irgDP [ n - 1 ] ;

    for ( int i = 3 ; i < n ; ++i )
    {
        irgDP [ 0 ] = irgDP [ 1 ] ;
        irgDP [ 1 ] = irgDP [ 2 ] ;
        irgDP [ 2 ] = ( irgDP [ 0 ] + irgDP [ 2 ] ) % 1000000007 ;
    }


    return irgDP [ 2 ] ;
}