[삼성 알고리즘] Dynamic Programming(2xn 타일링2)

안녕하세요. 이번에 포스팅할 알고리즘은 동적프로그래밍 입니다.

 

동적 프로그래밍은 메모제이션을 통해 수학적인 식을 만들어서 알고리즘을 작성하는 것이 가장 기본적인 방법입니다.

 

여기서, 메모제이션을 간단히 설명드리자면..

메모제이션이란 바로 동적프로그래밍의 핵심으로 이전에 계산한 값을 메모리에 저장해둠으로써 다시 계산하지 않는 방법입니다. 즉 다시 말해 알고리즘에서는 한 번 계산한 값을 배열에 넣어두고 이 배열 값들을 바탕으로 다음 값을 구하고 또 이렇게 구한 값으로 다음 값을 구하는 효율적인 방법을 채택함으로써 빠른 속도의 좋은 알고리즘을 만들어 낼 수 있습니다.

 

때문에 기본적으로 동적 프로그래밍은 n일 때 값을 구하기 위해선 n-1, n-2 혹은 n+1 등의 값들을 이용해서 구해나갈 수 있으며 이 때 n 값 x(n)을 구하는 식을 수학적으로

ex x(n) = x(n-1) + x(n-2)*3과 같이 구해내는 것이 핵심입니다.

이후에는 해당 수학적 식에 맞게 간단히 코드만 작성하면 되기 때문에 상대적으로 코드 수도 짧으며 코드 작성에 대해서는 생각보다 어렵지 않게 구현할 수 있습니다.

 

이번 포스팅은 백준의 2xn 타일링2 문제를 바탕으로 진행하겠습니다.

 

1. 문제 이해

2xn 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수를 구하는 문제로

2xn의 직사각형의 갯수를 구할 때 이렇게 생각해 볼 수 있습니다.

 

2. 식 만들기

1) 2x(n-1)

먼저 2xn의 직사각형을 채우는 방법은 2x(n-1) 채우는 방법에 2x1 하나를 추가한 방법이 있을 수 있습니다.

 

2) 2x(n-2)

두 번 째로 2x2, 2x1을 추가하는 방법이 있는데 이는 2x(n-2)에서 2x2를 추가하거나 2x1을 두 번 추가하여 2xn을 만들 수 있습니다. 이 때 1x2 두 번을 통해서 만드는 경우가 있는데 이는 1)과 중복되는 값이라 반드시 제거해줘야 합니다.

 

2xn = 2x(n-1) + 2*2x(n-2)

 

결과적으로 위 수식을 얻을 수 있게 되고 이를 코드로 구현하면 됩니다.

 

 

3. 소스 코드

#include<iostream>

#include<cstdio>

 

using namespace std;

    long long arr[1001];

 

    

long long num_tile(int num) {

    if(arr[num] == -1) {

        arr[num] = (num_tile(num-1)+(2*num_tile(num-2)))%10007;

    }

    return arr[num];

}

int main (void) {

    int n;

    scanf("%d",&n);

 

    for(int i=0;i<1001;i++) {

        arr[i]=-1;

    }

    arr[1]=1;

    arr[2]=3;

 

    cout<<num_tile(n);

    return 0;

}