[C/C++] 백준 #2718 타일 채우기(동적계획법)

경우의 수를 알아내라는 문제들 상당수는 동적계획법(Dynamic Programming)으로 해결할 수 있습니다.

하지만 동적계획법을 사용하기 위해서는 문제를 올바르게 이해하는 것이 선행되어야 합니다.

 

Dynamic Programming

 

2xn일 때에는 피보나치 수열과 비슷한 점화식을 얻을 수가 있습니다.  하지만 3xn, 4xn 과 같이 수가 늘어나면 조금 더 복잡한 점화식이 필요합니다.

 

일단 제가 모델링한 것은 조금 복잡합니다.

이전값에 대해서 4개값까지 참고를 하니까요.

 

문제는 다음 링크와 같습니다.

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

 

프로그램 설명:

 

1. 함수 solve(int n)

 

• 이 함수는 주어진 n 크기의 바닥을 채우는 방법의 수를 계산하고 출력합니다.

• 이 문제에서는 특이한 점이 있는데, 점화식이 주어져 있고 이를 기반으로 방법의 수를 계산하게 됩니다.

 

점화식은 다음과 같이 했습니다.

\[f_0 = 1, f_1 = 1, f_2 = 5, f_3 = 11\]

\[f_n = f_{n-1} + 5f_{n-2} + f_{n-3} - f_{n-4}\]

 

이 점화식을 얻기 위해서는 조금 복잡한 방법을 써야 합니다.  두칸씩 삐져나오는 경우가 생기니까요.

그 경우를 만들고, 그것을 줄이는 작업을 통하여 위의 식을 얻게 됩니다.

 

계산 과정:

 

• n이 4보다 클 경우, 이 점화식을 활용하여 필요한 만큼 반복합니다.

• 배열 f를 갱신하는 과정이 반복되며, 매 반복마다 f[0]부터 f[3]까지의 값을 차례로 계산합니다.

• 각 반복마다 배열의 값이 갱신되면서 점화식에 맞춰서 계속해서 f[n] 값을 갱신하게 됩니다.

 

결과 출력:

 

• n이 4 이하일 경우, 바로 f[n%4] 값을 출력합니다.

• n이 4보다 클 경우, 위에서 계산된 f[n%4] 값을 출력합니다.

 

2. main() 함수

 

• 이 함수는 프로그램의 진입점으로, 여러 테스트 케이스를 처리합니다.

• 먼저 입력된 테스트 케이스의 수 t를 받고, 그에 맞춰서 n 값을 입력받아 각 n에 대해 solve(n) 함수를 호출합니다.

• solve(n) 함수는 각 n에 대한 타일 채우기 방법의 수를 계산하여 출력합니다.

 

이것을 통하여 만들어진 소스입니다.  사실 어느정도 큰 값에 대해서 미리 계산을 하고 바로 답을 주는 것이 더 빠르게 답을 냈 수 있습니다.

어느정도 N이 커짐에 따라서 기하급수적으로 경우의 수는 늘어나니까요.  N이 아마도 10 정도면 최대값의 수치가 만들어질겁니다.

//------------------------------------------------
//    baekjoon #2718 - Fill Tiles
//        - by Aubrey Choi
//        - created at 2019-07-28
//------------------------------------------------
#include <stdio.h>

//    f[n] = f[n-1]+5f[n-2]+f[n-3]-f[n-4];
void solve(int n)
{
    int f[4] = { 1, 1, 5, 11 };
    for(int i = 0; i < n/4; i++)
    {
        f[0] = f[3]+5*f[2]+f[1]-f[0];
        f[1] = f[0]+5*f[3]+f[2]-f[1];
        f[2] = f[1]+5*f[0]+f[3]-f[2];
        f[3] = f[2]+5*f[1]+f[0]-f[3];
    }
    printf("%d\n", f[n%4]);
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        solve(n);
    }
}