문제 개요
이 문제에서는 두 개의 정수 n과 m이 주어집니다. 여기서 n은 그려야 할 그림의 개수, m은 사용할 수 있는 색상의 개수를 의미합니다. 우리가 구해야 할 것은 인접한 두 그림이 같은 색으로 칠해지지 않도록 모든 그림을 칠할 수 있는 총 경우의 수입니다.
예제를 통해 문제를 자세히 살펴보겠습니다.
입력
n = 3, m = 3
출력
12
설명
P1 P2 P3
C1 C2 C3
C1 C3 C2
C1 C2 C1
C1 C3 C1
C2 C1 C2
C2 C3 C2
C2 C1 C3
C2 C3 C1
C3 C1 C3
C3 C2 C3
C3 C1 C2
C3 C2 C1
그림 3개와 색상 3개가 주어졌을 때, 인접한 그림끼리 색이 겹치지 않는 모든 조합은 위와 같이 총 12가지입니다.
접근 방법 및 해결 아이디어
첫 번째 그림은 사용 가능한 m가지 색상 중 어떤 색으로든 자유롭게 칠할 수 있습니다. 반면 두 번째 그림부터는 바로 앞 그림에 사용된 색 하나만 제외하면 되므로, 매번 (m-1)가지 색상 중에서 선택할 수 있습니다.
따라서 전체 경우의 수는 다음 공식으로 계산됩니다.
m × (m-1)(n-1)
예제에 대입해 보면 3 × 2² = 12가 되어, 앞서 확인한 출력 결과와 정확히 일치합니다.
C++ 구현 코드
아래는 위 접근 방식을 구현한 C++ 프로그램입니다. n이 커질 경우 결과값이 매우 커질 수 있으므로, 오버플로를 방지하기 위해 모듈러 연산(10⁹+7)과 함께 비트 연산 기반의 빠른 거듭제곱 기법을 사용했습니다.
예제 코드
#include <iostream>
#define modd 1000000007
using namespace std;
unsigned long calcPower(unsigned long base, unsigned long power, unsigned long p){
unsigned long result = 1;
base = base % p;
while (power > 0) {
if (power & 1)
result = (result * base) % p;
power = power >> 1;
base = (base * base) % p;
}
return result;
}
int colorPainting(int n, int m){
return calcPower(m - 1, n - 1, modd) * m % modd;
}
int main(){
int n = 5, m = 7;
cout<<"The number of ways to color the given paintings is : "<<colorPainting(n, m);
return 0;
}
출력 결과
The number of ways to color the given paintings is : 9072
코드 설명
- calcPower 함수: 비트 시프트 연산을 활용한 빠른 거듭제곱(모듈러 지수 연산) 함수로, O(log n)의 시간 복잡도로 (m-1)^(n-1) 값을 효율적으로 계산합니다.
- colorPainting 함수: 공식 m × (m-1)^(n-1)을 그대로 코드로 옮긴 핵심 로직으로, 최종 경우의 수를 반환합니다.
- modd 상수: 결과값이 지나치게 커지는 것을 막기 위해 10⁹+7로 나눈 나머지를 유지합니다.
n = 5, m = 7인 경우 7 × 6⁴ = 9072가 계산되어, 프로그램의 출력 결과와 일치하는 것을 확인할 수 있습니다.