[Python] 24187번 Korta vokaler

 

https://www.acmicpc.net/problem/24187

24187번: Korta vokaler

---

 

23/07/03

 

 

언어 장벽이 있는 스웨덴어 문제로, 다른 사람들의 풀이와는 다르게 푼 듯 하여 올려본다.

---

 

문제 접근 방식:

 

 

먼저, 문제를 요약해서 번역을 하자면 다음과 같다.

 

단어가 주어지면, 단어에 "단모음"이 없도록 글자를 없애는 방법의 수를 구해라.(단, 모든 글자를 없애면 안됨)
여기서 "단모음"은, 모음 뒤에 최소 2개 이상의 연속된 자음이 있을 때, "단모음"이라고 한다.
또한, "모음"은 "a, e, i, o, u, y"로만 제한한다.

제한:
단어 글자 수는 최대 50 임
또한, 방법의 수는 32비트 정수 형을 넘을 수도 있다는 사실에 유의해야 한다.

 

문제에서는 "글자를 없애는 방법의 수"라고 했지만, 나는 앞에서부터 문자열을 순회하며, 기존의 글자를 추가할 것인지, 추가하지 않을 것인지의 여부를 따지는 문제로 치환해서 생각했다.

 

입력 예시 1을 그린 트리의 일부분

 

DP문제이지만, 나는 이 문제를 그래프적인 관점에서 바라보아서 상태가 전이됨을 통해 문제를 해결하였다.

 

때문에, 상태의 경우를 다음과 같이 나누었다.

 

	이전 문자		현재 문자
$1$	자음	$\rightarrow$	자음
$2$	자음	$\rightarrow$	모음
$3$	모음	$\rightarrow$	자음
$4$	모음	$\rightarrow$	모음

 

그러고 나서 문자열을 순회하면서 현재 문자열이 자음인지 모음인지 여부만 판단해 주었다.

 

만약 현재 문자열이 자음이라면, 우리는 $1$번 상태는 $1$번 상태로 전이되고, $2$번 상태는 $3$번 상태로 전이되고, $4$번 상태는 $3$번 상태로 전이됨을 알 수 있다.

 

여기서 주의할 점은, 모음 뒤에는 자음이 $2$번 이상 올 수 없기 때문에, $3$번 상태에서 $1$번 상태로는 전이될 수 없다는 사실이다.

 

때문에 이에 대한 상황을 그래프로 도식화하면 다음과 같다.

 

현재 문자가 자음일 때 전이되는 모습

 

만약 현재 문자열이 모음이라면, 우리는 $1$번 상태는 $2$번 상태로 전이됨을 알 수 있고, $2$번 상태는 $4$번 상태로 전이 됨을 알 수 있으며, $3$번 상태는 $2$번 상태로, $4$번 상태는 $4$번 상태로 전이 됨을 알 수 있다.

 

이에 대한 상황을 그래프로 도식화하면 다음과 같다.

 

현재 문자가 모음일 때 전이 되는 모습

 

때문에 이를 Psuedo Code로 작성하면 다음과 같다.

 

if now char is vowel:
    state4 += state4
    state4 += state2
    state2 += (state1 + state3)
else:
    state1 += state1
    state3 += (state2 + state4)

 

이렇게 작성될 수 있는 이유는, 문자가 주어지면 우리는 그걸 추가함으로써 상태를 변화시킬 수도 있고, 추가하지 않음으로써 상태를 변화시키지 않을 수도 있기 때문에 기존에 있던 상태의 경우의 수에서 더해지기 때문이다.

 

이제 초기 상태가 어떤지 정의해야 하는데, 초기 상태는 $state1 = 1$이고, 나머지는 모두 $0$인 상태로 간주할 수 있다.

 

즉, 이전 문자열이 자음, 현재 문자열이 자음인 상태로 간주할 수 있는 것인데, 그 이유는 문제 제약 조건 상 자음 뒤에는 모음이든 자음이든 어떤 것이든 간에 와도 상관없는 반면, 모음 뒤에는 무엇인가 올 수 있는 조건이 한정되어 있기 때문에 그런 것이다.

 

또한, 우리는 아무것도 없는 문자열을 제외해야 하므로, 최종적으로 나오는 $sum(states)$에서 $1$을 빼줘야 한다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 24187번 Korta vokaler
# DP, 문자열
"""
접근 방법:
DAG
"""
vowel = {'a', 'e', 'i', 'o', 'u', 'y'}
state1, state2, state3, state4 = 1, 0, 0, 0
for char in input():
    if char in vowel:
        state4 += state4
        state4 += state2
        state2 += (state1 + state3)
    else:
        state1 += state1
        state3 += (state2 + state4)
print(state1 + state2 + state3 + state4 - 1)