알파벳 m개와 정수 n이 주어졌다고 가정해 봅시다. 이때 m개의 알파벳으로 만들 수 있는 길이 n의 문자열 중, 길이가 1보다 큰 회문(palindrome) 부분 문자열을 하나도 포함하지 않는 문자열의 개수를 구하는 것이 문제입니다. 답이 너무 커질 경우 결과를 10^9+7로 나눈 나머지를 반환합니다.
예를 들어 n = 2, m = 3이 입력으로 주어진다면 출력은 6이 됩니다. m = 3이므로 알파벳 집합이 {x, y, z}일 때 만들 수 있는 문자열은 [xx, xy, xz, yx, yy, yz, zx, zy, zz]입니다. 그런데 이 중 [xx, yy, zz]는 두 글자가 같아서 회문이 되므로 유효하지 않습니다. 따라서 유효한 문자열은 총 6개입니다.
접근 방법
핵심 아이디어는 다음과 같습니다. 길이가 1보다 큰 회문 부분 문자열이 없으려면 다음 두 조건을 만족해야 합니다.
- 인접한 두 문자가 같으면 안 됩니다. (길이 2의 회문 방지)
- 바로 앞의 문자와도 같으면 안 됩니다. 즉, 각 위치의 문자는 자신의 앞 두 문자와 달라야 합니다. (길이 3의 회문 방지)
첫 번째 문자는 m가지 선택이 가능하고, 두 번째 문자는 첫 번째와 달라야 하므로 (m-1)가지 선택이 가능합니다. 세 번째 문자부터는 앞 두 문자와 모두 달라야 하므로 각 위치마다 (m-2)가지 선택이 가능합니다. 따라서 전체 경우의 수는 다음 공식으로 계산할 수 있습니다.
- p := 10^9 + 7
- n이 1이면 → m mod p를 반환
- n이 2이면 → m × (m-1) mod p를 반환
- m ≤ 2이면 → 0을 반환 (두 글자만으로는 회문 없는 문자열을 길게 만들 수 없음)
- 그 외의 경우 → m × (m-1) × ((m-2)^(n-2) mod p) mod p를 반환
예제 코드
다음 Python 구현을 통해 더 잘 이해할 수 있습니다.
def solve(n, m):
p = 10**9+7
if n == 1:
return m % p
if n == 2:
return m * (m - 1) % p
if m <= 2:
return 0
return m * (m - 1) * pow(m - 2, n - 2, p) % p
n = 2
m = 3
print(solve(n, m))입력
n = 2, m = 3
출력
6
복잡도 분석
이 풀이는 pow 함수를 사용한 거듭제곱 계산에 O(log n)의 시간이 걸리며, 추가 메모리 사용은 O(1)입니다. 따라서 n이 매우 큰 경우에도 효율적으로 답을 구할 수 있습니다.