C 프로그래밍으로 인접한 그림끼리 색이 겹치지 않도록 N개의 그림을 칠하는 경우의 수 구하기

문제 개요

이 문제에서는 N개의 그림과 사용할 수 있는 m가지 색상이 주어지며, 인접한 그림끼리는 서로 같은 색이 되지 않도록 모든 그림을 칠하는 경우의 수를 구해야 합니다.

그런데 입력값이 커지면 경우의 수 역시 기하급수적으로 늘어나기 때문에, 이 값을 그대로 다루기는 어렵습니다. 이를 해결하기 위해 경쟁 프로그래밍에서 널리 쓰이는 표준 방법인 모듈로 연산을 적용해, 정답을 10⁹ + 7(1,000,000,007)로 나눈 나머지로 계산합니다.

접근 방식과 공식

규칙을 단계별로 살펴보면 다음과 같습니다.

• 첫 번째 그림은 제약 없이 m가지 색상 중 아무거나 선택할 수 있습니다.
• 두 번째 그림부터는 바로 앞 그림과 색이 달라야 하므로, 매번 (m − 1)가지 색상만 고를 수 있습니다.
• 나머지 (n − 1)개의 그림에 대해서도 각각 (m − 1)가지씩 선택지가 존재합니다.

따라서 전체 경우의 수를 구하는 공식은 다음과 같습니다.

Ways = m × (m − 1)^(n − 1)

예제

그림의 개수 n과 색상의 개수 m이 주어졌을 때의 동작을 확인해 보겠습니다.

입력

n = 5 , m = 6

출력

3750

계산 과정은 다음과 같습니다.

Ways = 6 × (6 − 1)^4 = 6 × 625 = 3750

C++ 구현 코드

아래 코드는 위 공식을 반복 제곱(빠른 거듭제곱) 기법으로 구현한 것입니다.

#include <iostream>
#include <math.h>
#define modd 1000000007
using namespace std;

unsigned long find(unsigned long x,
unsigned long y, unsigned long p) {
    unsigned long res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

int ways(int n, int m) {
    return find(m - 1, n - 1, modd) * m % modd;
}

int main() {
    int n = 5, m = 6;
    cout << "There are " << ways(n, m) << " ways";
    return 0;
}

코드 설명

• find 함수: 지수를 절반씩 줄여 가면서 거듭제곱을 계산하므로, (x^y) mod p를 O(log y) 시간 안에 구할 수 있습니다. 매 연산 후 p로 나눈 나머지를 저장해 값이 무한정 커지는 것을 방지합니다.
• ways 함수: 공식 m × (m − 1)^(n − 1) mod (10^9 + 7)을 그대로 적용합니다.
• main 함수: 예제 입력(n = 5, m = 6)으로 결과를 화면에 출력합니다.

실행 결과

There are 3750 ways

시간 복잡도

핵심 연산인 모듈러 거듭제곱이 지수 크기에 대해 로그 시간에 수행되므로, 전체 알고리즘의 시간 복잡도는 O(log n)입니다. 덕분에 n과 m이 매우 큰 값이라도 효율적으로 정답을 구할 수 있습니다.