문제 설명
숫자 n이 주어졌을 때, 다음 규칙에 따라 길이가 n인 문자열을 총 몇 개 생성할 수 있는지 구하는 프로그램을 작성해 보겠습니다.
- 모든 문자는 소문자 모음 [a, e, i, o, u] 중 하나여야 합니다.
- 'a' 뒤에는 'e'만 올 수 있습니다.
- 'e' 뒤에는 'a' 또는 'i'만 올 수 있습니다.
- 'i' 뒤에는 'i'가 연속해서 올 수 없습니다.
- 'o' 뒤에는 'i' 또는 'u'만 올 수 있습니다.
- 'u' 뒤에는 'a'만 올 수 있습니다.
결과값이 매우 커질 수 있으므로, 최종 답은 10^9 + 7로 나눈 나머지를 반환합니다.
예를 들어 입력이 n = 2라면 출력은 10이 됩니다. 다음과 같은 두 글자 문자열을 만들 수 있기 때문입니다.
["ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou", "ua"]
풀이 접근 방법
이 문제는 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 각 모음으로 끝나는 문자열의 개수를 변수로 관리하고, 이전 단계의 값을 이용해 다음 단계 값을 갱신하는 방식입니다. 핵심 아이디어는 다음과 같습니다.
- m = 10^9 + 7을 정의합니다.
- n이 0이면 0을 반환합니다.
- 각각 'a', 'e', 'i', 'o', 'u'로 끝나는 문자열의 개수를 저장할 다섯 개의 변수 a, e, i, o, u를 선언하고 모두 1로 초기화합니다(길이 1인 문자열은 각 모음 하나씩 총 5개).
- n-1번 반복하면서 다음 규칙에 따라 값을 동시에 갱신합니다.
- a := e + i + u ('a' 앞에는 'e', 'i', 'u'가 올 수 있음)
- e := a + i ('e' 앞에는 'a', 'i'가 올 수 있음)
- i := e + o ('i' 앞에는 'e', 'o'가 올 수 있음)
- o := i ('o' 앞에는 'i'만 올 수 있음)
- u := i + o ('u' 앞에는 'i', 'o'가 올 수 있음)
- 최종적으로 (a + e + i + o + u) mod m을 반환합니다.
주의할 점은 갱신 시 이전 단계의 값을 기준으로 한 번에 동시에 업데이트해야 한다는 것입니다. 파이썬의 다중 할당(multiple assignment)을 활용하면 임시 변수 없이 깔끔하게 처리할 수 있습니다.
구현 예제
class Solution:
def solve(self, n):
m = (10 ** 9 + 7)
if n == 0:
return 0
a = e = i = o = u = 1
for _ in range(n-1):
a, e, i, o, u = e+i+u, a+i, e+o, i, i+o
return (a + e + i + o + u) % m
ob = Solution()
print(ob.solve(3))
입력
3
출력
19
동작 과정 살펴보기
n = 3일 때의 계산 흐름을 확인해 보겠습니다.
- 초기 상태(n = 1): a = e = i = o = u = 1, 합계는 5
- 1회 반복 후(n = 2): a = 3, e = 2, i = 2, o = 1, u = 2, 합계는 10
- 2회 반복 후(n = 3): a = 6, e = 5, i = 3, o = 2, u = 3, 합계는 19
이처럼 각 반복마다 O(1)의 연산만 수행하므로, 전체 시간 복잡도는 O(n)이며 공간 복잡도 역시 O(1)로 매우 효율적입니다. n이 큰 값이 주어져도 빠르게 답을 구할 수 있습니다.