n × 3 크기의 그리드가 있고, 각 칸을 빨강(Red), 노랑(Yellow), 초록(Green) 세 가지 색 중 정확히 하나로 칠하려고 합니다. 단, 인접한 두 칸은 서로 다른 색이어야 한다는 제약 조건이 있습니다. 그리드의 행 개수 n이 주어졌을 때, 이 그리드를 칠할 수 있는 서로 다른 방법의 수를 구하는 것이 문제입니다. 답이 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 1이라면 출력은 12가 됩니다.
문제 접근 방법
이 문제의 핵심 아이디어는 각 행의 색 배치를 두 가지 유형으로 분류하는 것입니다.
- ABA 유형: 첫 번째 칸과 세 번째 칸이 같은 색인 경우 (예: 빨강-노랑-빨강)
- ABC 유형: 세 칸이 모두 서로 다른 색인 경우 (예: 빨강-노랑-초록)
행이 하나뿐일 때(n = 1) ABA 유형은 3 × 2 = 6가지, ABC 유형 역시 3 × 2 × 1 = 6가지이므로 전체 경우의 수는 12가지입니다.
행이 늘어날 때의 전이 관계는 다음과 같습니다.
- 현재 행이 ABA 유형이면 → 다음 행은 ABA 유형 3가지 또는 ABC 유형 2가지 가능
- 현재 행이 ABC 유형이면 → 다음 행은 ABA 유형 2가지 또는 ABC 유형 2가지 가능
알고리즘 단계
위의 전이 관계를 활용하면 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 풀이 과정은 다음과 같습니다.
- m = 10^9 + 7로 설정합니다.
- add() 함수를 정의합니다. 이 함수는 ((a mod m) + (b mod m)) mod m을 반환하여 오버플로우를 방지합니다.
- 메인 함수에서 다음을 수행합니다.
- a123 := 6, a121 := 6으로 초기화합니다. (각각 ABC 유형, ABA 유형 행의 경우의 수)
- i := 2부터 n까지 반복하며 다음을 수행합니다.
- b121 := add(3 * a121, 2 * a123)
- b123 := add(2 * a121, 2 * a123)
- a121 := b121, a123 := b123으로 갱신합니다.
- 최종적으로 add(a123, a121)을 반환합니다.
아래 예제 코드를 통해 더 잘 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ((a % mod) + (b % mod)) % mod;
}
int numOfWays(int n){
lli a123 = 6, a121 = 6;
lli b123, b121;
for (int i = 2; i <= n; i++) {
b121 = add(3 * a121, 2 * a123);
b123 = add(2 * a121, 2 * a123);
a121 = b121;
a123 = b123;
}
return add(a123, a121);
}
};
main(){
Solution ob;
cout << (ob.numOfWays(3));
}입력
3
출력
246
복잡도 분석
- 시간 복잡도: O(n) — 행 개수에 비례하여 한 번씩 순회합니다.
- 공간 복잡도: O(1) — 상수 개수의 변수만 사용하므로 추가 메모리가 필요하지 않습니다.