[Python] 30518번 짜고 치는 가위바위보 (Small)

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

30518번: 짜고 치는 가위바위보 (Small)

---

 

23/11/05

 

 

내가 만든 문제다.

---

 

문제 접근 방식:

 

 

먼저 문제부터 읽어보자. 문제는 Large버전과 동일하다. 다만 제한이 조금 다르다.

 

제한에 주목해 보자. 제한은 $N = 20$까지인 것을 확인할 수 있다.

 

관객들이 분노하지 않는 경우는 오직 smallant가 내고자 하는 가위바위보 정보에 달려 있음을 알고 있고, 이를 부분적으로 취하는 경우의 수는 $2^N$개라는 것을 알고 있다. (부분집합의 개수)

 

따라서, 기껏 해봤자 최대 $2^{20}$개의 경우의 수만 따져주어서, 이를 그대로 문제 조건에 맞는지 맞지 않는지만 따져주어도 충분하다.

 

그렇다면 모든 경우의 수를 어떻게 따져 주어야 할까?

 

비트마스킹을 이용한 방법(취하는 것을 1, 취하지 않는 것을 0으로 보고 하나의 상태를 2진법의 수로 간주하여 모든 경우의 수를 돌아보는 방법)도 있을 수 있겠지만, 여기서는 파이썬의 itertools모듈을 활용한 방법을 소개하고자 한다.

 

파이썬의 itertools모듈에는 combinations라는 아주 좋은 함수가 있다. 이 함수는 보통 조합으로 해결할 수 있는 백트래킹 문제에서 자주 쓰이는 함수이다. 

 

이 함수는 인자로 두 개의 값을 받는다. 하나는 뽑을 객체(이 객체는 반복 가능한 객체여야 한다)와 또 하나는 그 객체에서 몇 개를 뽑을 것인가이다.

 

그렇게 뽑을 객체에서 일정한 개수 만큼을 뽑는 모든 경우(이때 하나의 경우는 하나의 튜플로 나온다.)를 사전 순 정렬로 하여 하나의 반복가능한 객체를 내보내는 것이 combinations 함수의 역할이다.

 

즉, 다음과 같은 역할을 수행한다.

 

combinations(iterable, how_many_pick_in_iterable) -> iterable

 

smallant가 가지고 있는 문자열의 정보가 총 $N$개라고 하면, 우리는 smallant가 취할 수 있는 문자열의 개수는 총 $1$개부터 $N$개까지임을 알고 있으므로, 뒤에 얼마나 많은 개수를 뽑을 것인가만 $1$개부터 $N$개까지 조절해 가며 모든 경우의 수를 찾아낼 수 있다.

 

즉, 다음과 같은 2중 for문으로 구현이 될 것이다.

 

for how_many_pick in range(1, len(smallant)+1):
    for tuple in combinations(range(len(smallant)), how_many_pick):
    	code...

 

여기서 주목할 것은 내가 combinations에 넣는 반복 가능한 객체가 range객체라는 것이다.

 

어차피 smallant의 정보가 문자열로 주어지니, 그 인덱스만 따지면 충분하다는 논리이다.

 

또한 순서를 따져서 그대로 합친다고 했으니, 순서 또한 중요하다.

 

즉, 몇 번째에 있는가가 필요하니 그냥 인덱스를 combinations함수에 넣은 것이라고 생각하면 될 것이다.

 

이후의 코드는 그렇게 나온 인덱스의 튜플을 사용해 라운드를 일부분만 취했을 때의 경기를 재구성하는 코드이다.

 

이 경기가 조건을 만족하려면 연속된 세 개의 문자열이 'RSS', 'SPP', 'PRR'이면 안된다.

 

이 조건을 따져주어서 이 경기가 관중들이 화나지 않도록 하는 경기인지, 그렇지 않은 경기인지를 따져주면 충분하다.

  

---

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

# RPS-나이브한 코드
import sys
input = sys.stdin.readline
from itertools import combinations

MOD = 1_000_000_007

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

total_string = lighter + smallant
# 나이브한 솔루션
avail = 0
for how_many_pick in range(1, len(smallant)+1):
    for tpl in combinations(range(len(smallant)), how_many_pick):
        string = lighter
        for idx in tpl:
            string += smallant[idx]
        # 가능한지 판별
        is_ok = True
        for i in range(len(string)-2):
            a, b, c = string[i], string[i+1], string[i+2]
            if a == 'R' and b == 'S' and c == 'S':
                is_ok = False
                break
            if a == 'S' and b == 'P' and c == 'P':
                is_ok = False
                break
            if a == 'P' and b == 'R' and c == 'R':
                is_ok = False
                break
        if is_ok:
            avail += 1
print(avail % MOD)