[Python] 30519번 짜고 치는 가위바위보 (Large)

 

 

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

30519번: 짜고 치는 가위바위보 (Large)

---

 

23/11/05

 

 

내가 제작한 문제다. Small버전에 대한 해설은 아래 링크에 있으니 궁금하다면 확인해 보자.

 

2023.11.25 - [알고리즘/백준 문제 풀이] - [Python] 30518번 짜고 치는 가위바위보 (Small)

 

---

 

문제 접근 방식:

 

 

문제 제한을 주목해 보자. 이전 문제는 제한이 $N = 20$이었던 반면, 이 문제의 경우 $N = 1,000,000$이다.

 

즉, 모든 경우의 수인 $2^{1,000,000}$를 다 돌아보며 가능한 지 가능하지 않은 지를 따지기에는 너무나도 오랜 시간이 소요된다.

 

이럴 때에는 어떻게 해결해야 할까?

 

시간제한이 $1$초이기 때문에 대략 $\mathcal{O}(N)$의 시간 복잡도로 해결해야만 한다.

 

즉, 문자열이 주어진 다면 그 문자열을 하나하나 바로 보면서 경우의 수를 따져야만 한다.

 

결론을 이야기하자면, 이 문제는 DP로 해결할 수 있다. DP는 다들 알다시피 상태의 전이이기 때문에 DAG로 모델링 될 수 있고, 이 글에서는 그런 방식으로 설명할 것이다. 

 

이 문제의 아이디어는 아래 문제의 아이디어에서 영감을 받았다.

 

2023.07.04 - [알고리즘/백준 문제 풀이] - [Python] 24187번 Korta vokaler

[Python] 24187번 Korta vokaler

 

위의 문제에 대한 해설을 살펴보고 오는 것을 추천한다.

 

이 문제 또한 가위바위보의 정보를 일부분 취하는 경우의 수기 때문에, 문자열을 없앤다고 생각을 하는 것이 아니라 하나씩 보면서 추가하는 방향으로 생각해도 된다.

 

따라서 문자열을 하나하나 살펴보면서 이전 문자와 현재 문자가 어떤 상태였는지에 따라서 다음과 같은 $9$가지의 경우로 나눌 수 있다.

 

9가지 상태

 

이 9가지 상태를 토글링으로 순환시키며 DP값을 구하면 된다.

 

만약 현재 순회하는 문자가 주먹이라면, 위의 $9$가지 상태는 다음 그래프와 같이 서로 전이됨을 확인할 수 있다.

 

현재 문자가 주먹일 때의 상태 전이

 

이렇게 전이되는 이유는, 현재 문자가 주먹으로 들어온다면 이전에 "현재 문자열이 가위로 끝났던 상태"들은 모두 4번 상태(이전 문자가 가위이고 현재 문자가 주먹인 상태)로 전이되고, 이전에 "현재 문자열이 보로 끝났던 상태"들은 모두 7번 상태(이전 문자가 보이고 현재 문자가 주먹인 상태)로 전이되기 때문이다.

 

마찬가지로 4번 상태는 1번 상태로 전이되고, 1번 상태는 자기 자신으로 돌아온다.

 

하지만 우리는 이긴 뒤 비기면 안 된다는 조건을 만족시켜야 하므로, 보 $\rightarrow$ 주먹 $\rightarrow$ 주먹으로 이어지는 상태를 만들면 안 된다.

 

따라서 7번 상태는 4번 상태와는 다르게 1번 상태로 전이되지 않는다.

 

이와 똑같은 원리로, 우리는 현재 문자가 가위일 때와 보일 때의 상태 전이 또한 그래프로 확인할 수 있다.

 

이는 다음과 같다.

 

현재 문자가 가위일 때의 상태 전이

현재 문자가 보일 때의 상태 전이

 

초기 상태를 생각해 보면 이는 lighter가 처음 무엇을 내느냐에 따라 다르다.

 

lighter가 처음에 주먹을 낸 다면 1번 상태를 1로 초기화해 주면 되고, 가위를 낸다면 5번 상태를 1로, 보를 낸다면 9번 상태를 1가지로 초기화해주면 된다.

 

그 이유는 1, 5, 9번 상태는 모두 자기 자신으로 돌아오는 상태이고, 우리는 lighter이전의 문자열이 없긴 하지만 저렇게 간주해도 문제의 조건을 만족시키는 데에는 문제가 없기 때문이다.(다른 문자열의 상태를 1로 간주하면 상태 전이를 하면서 문제가 생기게 된다.)

 

따라서 문자열을 순회할 때마다 9가지의 상태를 모두 토글링하며 구현해 주면 된다.

 

---

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

# RPS-Large 정해
import sys
input = sys.stdin.readline
MOD = 1_000_000_007

lighter = input().rstrip()
smallant = input().rstrip()

total_string = lighter + smallant

states = [0 for _ in range(10)]
if total_string[0] == 'R': states[1] = 1
elif total_string[0] == 'S': states[5] = 1
else: states[9] = 1

for i in range(1, len(total_string)):
    if total_string[i] == 'R':
        states[1] += states[1]
        states[1] %= MOD
        states[1] += states[4]
        states[1] %= MOD
        states[4] += (states[2] + states[5] + states[8]) % MOD
        states[4] %= MOD
        states[7] += (states[3] + states[6] + states[9]) % MOD
        states[7] %= MOD
    elif total_string[i] == 'S':
        states[5] += states[5]
        states[5] %= MOD
        states[5] += states[8]
        states[5] %= MOD
        states[8] += (states[3] + states[6] + states[9]) % MOD
        states[8] %= MOD
        states[2] += (states[1] + states[4] + states[7]) % MOD
        states[2] %= MOD
    else:
        states[9] += states[9]
        states[9] %= MOD
        states[9] += states[3]
        states[9] %= MOD
        states[3] += (states[1] + states[4] + states[7]) % MOD
        states[3] %= MOD
        states[6] += (states[2] + states[5] + states[8]) % MOD
        states[6] %= MOD

print((sum(states)-1)%MOD)