타일 채우기 | 백준 2133번

#include<cstdio>

int main(void)
{
    int n;
    int result[31]={0};
    int sum=0;// sum = result[0] + result[2] + ... + result[k];
    scanf("%d", &n);
    
    result[0] = 1;
    result[2] = 3;
    sum = result[0] + result[2];
    
    for(int i=4; i<=n; i=i+2)
    {
        result[i] = result[i-2] + 2*sum;// = 3result[i-2] + 2*sum[0 ~ i-4]
        sum += result[i];
    }
    
    printf("%d\n", result[n]);
    
    return 0;
}

배열 초기화를 하지 않아.. 2시간을 보냈다..
문제는 3xN 벽 채우기인데, N이 홀수인 경우 채울 수 없으므로 답은 0이어야 하는데, 난 홀수는 안물어볼 줄 알았다. 이거 초기화 안한걸로 혼자 엄청 고민하다가.. 혹시나 해서 초기화 했는데 역시나 하고 답이 되었다.
배열은 가독성을 위해 2, 4, 6, 8 ~ 30 까지 사용하였다. 이를 위해 result[31]까지 선언했다.
메모리를 줄이기 위해서라면 15개 배열로도 충분할 것 같다.
코드는 사실 주석에 달아놨다. 풀이를 하자면 아래와 같다.

result를 A라고 했을때 A[N] = A[N-2]*3 + A[N-4]*2 + A[N-6]*2 + ... A[2]*2 + 2 이다.
그 이유는 2칸이 확장될 경우, 채울 수 있는 경우가 3개가 있고,(따라서 N-2인 경우에 3을 곱함)
A[N-2]인 경우로 판단할 수 없는, A[N-2]칸에서 나뉘지 않는, 예를 들었을 때 위의 그림에서 A[N-4]의 저 상황과 같은 경우 2개의 경우의 수를 각각 갖는다.
이는 그 아래로 갈 경우에도 위와 같이 마찬가지이다.
따라서 코드에서 sum = 1+ result[2]로 시작하게 하였고, result[i] = 3*result[i-2] + 2*(result[i-4] ~ result[0])인데, sum이 result[i-2]를 포함하므로, 위와 같은 식이 나왔다.

성능개선을 위해서라면... 이걸 계산해서 단일 식으로 만들 수 도 있지 않을까 싶다.(크게 그럴 필요까진 없다고 본다.)

알고리즘 분류 : 다이나믹 프로그래밍

make better code

타일 채우기 | 백준 2133번

Artikel Menarik Lainnya