🎨 초보자 친화 가이드 'Number of Ways to Paint N 3 Grid' – LeetCode 1411 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

주어진 조건:

• n 행, 3 열인 격자.
• 사용할 수 있는 색은 빨강, 노랑, 초록 총 3가지.
• 인접한 두 셀(가로 또는 세로)은 같은 색을 가질 수 없다는 규칙.

목표

• 전체 격자를 색칠하는 모든 경우의 수를 계산한다.
• 결과는 (10^9+7) 로 나눈 나머지를 반환한다.

Intuition

각 행에 셀은 3개뿐이므로, 모든 유효한 행은 두 가지 패턴 중 하나에 속한다:

행 i 아래에 행 i + 1 을 놓을 때, 기존 행을 깨뜨리지 않으면서 새 행을 배치할 수 있는 경우를 세면:

• ABA 행 아래: 가능한 ABA 행 3가지, 가능한 ABC 행 2가지.
• ABC 행 아래: 가능한 ABA 행 2가지, 가능한 ABC 행 2가지.

ABA와 ABC 행의 개수만 유지하고 각 추가 행마다 업데이트하면 선형 시간 해결책을 얻을 수 있다.

Code Blocks

C++

class Solution {
public:
    int numOfWays(int n) {
        constexpr int kMod = 1000000007;
        long color2 = 6; // ABA patterns
        long color3 = 6; // ABC patterns

        for (int i = 1; i < n; ++i) {
            long next_color2 = (color2 * 3 + color3 * 2) % kMod;
            long next_color3 = (color2 * 2 + color3 * 2) % kMod;
            color2 = next_color2;
            color3 = next_color3;
        }
        return (color2 + color3) % kMod;
    }
};

Python

k_mod = 10**9 + 7
# color2 = ABA patterns, color3 = ABC patterns
color2 = 6
color3 = 6

for _ in range(1, n):
    next_color2 = (color2 * 3 + color3 * 2) % k_mod
    next_color3 = (color2 * 2 + color3 * 2) % k_mod
    color2, color3 = next_color2, next_color3

result = (color2 + color3) % k_mod

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var numOfWays = function(n) {
    const kMod = 1000000007n; // BigInt for safety
    let color2 = 6n; // ABA
    let color3 = 6n; // ABC

    for (let i = 1; i < n; i++) {
        const nextColor2 = (color2 * 3n + color3 * 2n) % kMod;
        const nextColor3 = (color2 * 2n + color3 * 2n) % kMod;
        color2 = nextColor2;
        color3 = nextColor3;
    }

    return Number((color2 + color3) % kMod);
};

Key Takeaways

• State Reduction: 행 구성을 ABA와 ABC 패턴으로 묶음으로써 개별 색 조합을 모두 추적할 필요가 없다.
• Linear Time Complexity: 알고리즘은 O(n) 시간에 동작하며 행을 한 번만 순회한다.
• Modulo Arithmetic: 각 단계마다 모듈러 연산을 적용해 카운트가 기하급수적으로 커지는 것을 방지한다.

Final Thoughts

이 문제는 상태 전이 동적 프로그래밍을 배우기에 훌륭한 입문 사례이다. 인접한 개체가 서로 달라야 하는 자원 스케줄링이나 지도 색칠 알고리즘 등 실제 상황에서도 비슷한 패턴 카운팅 기법이 등장한다. 이러한 카운팅 문제를 마스터하는 것은 최고 수준 기업의 기술 면접을 성공적으로 통과하는 데 큰 도움이 된다.