문제 소개
n × 3 크기의 그리드가 있고, 그리드의 모든 칸을 빨강(Red), 노랑(Yellow), 초록(Green) 세 가지 색 중 정확히 하나로 칠하려고 합니다.
여기에는 한 가지 제약 조건이 있습니다. 가로 또는 세로로 인접한 두 칸은 서로 같은 색이어서는 안 된다는 것입니다. 그리드의 행 개수 n이 주어졌을 때, 이 그리드를 조건에 맞게 칠할 수 있는 방법의 총 개수를 구해야 합니다. 답은 매우 커질 수 있으므로 109 + 7로 나눈 나머지를 반환합니다.
예를 들어 입력이 1이라면, 한 행을 칠하는 경우의 수는 총 12가지이므로 출력은 12가 됩니다.
접근 방법: 다이나믹 프로그래밍
각 행의 색 배치 패턴은 두 가지 유형으로 나눌 수 있습니다.
- a121 유형 (ABA 패턴): 첫 번째 칸과 세 번째 칸의 색이 같고, 가운데 칸만 다른 패턴입니다. 예: 빨강-노랑-빨강. 반복되는 색 3가지 × 가운데 색 2가지 = 6가지입니다.
- a123 유형 (ABC 패턴): 세 칸이 모두 서로 다른 색인 패턴입니다. 예: 빨강-노랑-초록. 3! = 6가지입니다.
따라서 n = 1일 때 초기값은 a121 = 6, a123 = 6입니다.
다음 행으로 넘어갈 때의 전이 관계는 다음과 같습니다.
- 이전 행이 ABA 패턴이면 → 다음 행이 ABA 패턴이 되는 경우는 3가지, ABC 패턴이 되는 경우는 2가지입니다.
- 이전 행이 ABC 패턴이면 → 다음 행이 ABA 패턴이 되는 경우는 2가지, ABC 패턴이 되는 경우는 2가지입니다.
이를 점화식으로 표현하면 다음과 같습니다.
- b121 = (3 × a121 + 2 × a123) mod m
- b123 = (2 × a121 + 2 × a123) mod m
2행부터 n행까지 반복한 뒤, 최종적으로 (a121 + a123) mod m을 반환하면 됩니다.
알고리즘 단계
- m = 109 + 7로 설정합니다.
- add(a, b) 함수를 정의합니다. 이 함수는 ((a mod m) + (b mod m)) mod m을 반환하여 오버플로를 방지합니다.
- 초기값을 a123 = 6, a121 = 6으로 설정합니다.
- i = 2부터 n까지 반복하면서 다음을 수행합니다.
- b121 = add(3 × a121, 2 × a123)
- b123 = add(2 × a121, 2 × a123)
- a121 = b121, a123 = b123으로 갱신합니다.
- 최종 결과로 add(a123, a121)을 반환합니다.
C++ 구현 예시
아래 구현을 통해 더 잘 이해해 보겠습니다.
#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
복잡도 분석
이 알고리즘은 행 개수 n에 대해 한 번의 선형 반복만 수행하므로 시간 복잡도는 O(n)이며, 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 n이 매우 큰 경우에도 효율적으로 동작합니다.