[프로그래머스] 258705 산 모양 타일링 (C/C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258705

풀이

문제를 처음 읽었을 때, 전체 타일을 왼쪽에서 오른쪽으로 확장해 가며 경우의 수를 세는 동적 계획법(DP)으로 접근할 수 있다고 생각했다.

처음에는 단일 상태로 아래와 같이 간단한 점화식을 세웠다.

여기서

• 2는 “마름모를 놓지 않거나, 오른쪽으로만 1개 놓는 경우”
• tops[n]은 “위쪽에 마름모를 1개 놓는 경우” 를 의미한다.

$n = 0$

$n = 1$

$n = 2$

위 그림에서

• $n = 0$일 때는 마름모를 0개, 왼쪽·오른쪽·위쪽 중 1개를 배치하는 총 4가지,
• $n = 1$일 때는 마름모를 0개, 오른쪽으로 1개 배치하는 총 2가지,
• $n = 2$일 때도 $n = 1$과 마찬가지로 2가지 경우의 수가 가능하다.

따라서, $f(0) = 4$, $f(1) = f(0) * 2 = 8$, $f(2) = f(1) * 2 = 16$이 된다.

하지만 이 식은 아래 이미지와 같이 이전 상태의 오른쪽 삼각형과 새 상태의 가운데 삼각형이 맞물리는 경우를 고려하지 못했다. 즉, 다음 단계에서 왼쪽으로 이어 붙이는 마름모가 전혀 반영되지 않는다는 점을 깨달았다.

이를 반영한 점화식을 세우려다가 현재와 같은 단일 상태에서는 점화식을 세우기 어렵다는 판단이 들어 상태를 세분화했다.

새로 들어오는 모양에서 기존 모양과 연결되는 부분에, 즉 왼쪽 방향으로 배치할 수 있음을 고려하여 이전 상태에서 오른쪽 방향으로 마름모가 배치 됐는지 아닌지를 알 필요가 있었다.

따라서 상태를 아래와 같이 4가지로 나누었다.

1. 마름모가 배치되지 않은 상태
2. 왼쪽 방향에 마름모가 배치된 상태
3. 오른쪽 방향에 마름모가 배치된 상태
4. 위쪽 방향에 마름모가 배치된 상태

문제를 다 풀고 이 글을 적으면서 생각해보니, 상태를 4가지로 정의하지 않고 마름모가 오른쪽에 배치된 상태와 그렇지 않은 상태 2가지로 정의했어도 같은 결과를 낼 수 있을 것 같다.

소스 코드

#include <bits/stdc++.h>

#define MOD 10007

typedef enum e_direction {
    NOTHING = 0,
    LEFT = 1,
    RIGHT = 2,
    UP = 3,
}   t_direction;

int solution(int n, std::vector<int> tops) {
    std::array<int, 4> prev = { 1, 1, 1, tops[0] }, curr;

    for (size_t i = 1; i < n; i++) {
        curr[NOTHING] = curr[RIGHT] = curr[UP] = (
            prev[NOTHING] + prev[LEFT] + prev[RIGHT] + prev[UP]
        ) % MOD;
        curr[UP] *= tops[i];
        curr[LEFT] = (prev[NOTHING] + prev[LEFT] + prev[UP]) % MOD;
        prev = curr;
    }

    return std::accumulate(prev.begin(), prev.end(), 0) % MOD;
}