BOJ 2930 - 가위 바위 보

문제

BOJ 2930 - 가위 바위 보

R라운드 가위바위보 게임에서 상근이의 실제 점수와, 각 라운드를 독립적으로 최적 선택했을 때의 최대 점수를 구하라. 이기면 2점, 비기면 1점, 지면 0점이다.

입력

라운드 수 R, 상근이의 선택 문자열, 친구 수 N, 각 친구의 선택 문자열이 주어진다. R, S, P는 각각 바위, 가위, 보를 뜻한다.

출력

상근이의 실제 총점과 최적 전략 총점을 각각 한 줄에 출력한다.

예제

풀이

각 라운드마다 실제 점수를 계산하고, 동시에 R/S/P 세 가지 선택의 점수를 모두 시뮬레이션하여 최대값을 구한다.

1. 가위바위보의 승리 관계를 (rsp[내 수] + 1) % 3 == rsp[상대 수]로 판정한다 (R=0, S=1, P=2 순환)
2. 각 라운드에서 상근이의 실제 선택에 대한 점수를 모든 친구와 비교하여 합산한다
3. 동시에 R, S, P 세 선택 각각에 대해서도 모든 친구와의 점수를 계산한다
4. 세 선택 중 최대 점수를 해당 라운드의 최적 점수로 누적한다

핵심 아이디어: 각 라운드는 독립적이므로, 라운드별로 가장 높은 점수를 주는 선택을 고르면 최대 점수가 된다.

코드

r = int(input())
s = input()
n = int(input())
fs = [input() for _ in range(n)]
 
rsp = {"R": 0, "S": 1, "P": 2}
 
cs = ms = 0
for i in range(r):
    ts = [[0, "R"], [0, "S"], [0, "P"]]
    for j in range(n):
        if (rsp[s[i]] + 1) % 3 == rsp[fs[j][i]]:
            cs += 2
        elif s[i] == fs[j][i]:
            cs += 1
 
        for t in ts:
            if (rsp[t[1]] + 1) % 3 == rsp[fs[j][i]]:
                t[0] += 2
            elif t[1] == fs[j][i]:
                t[0] += 1
    ms += max(ts)[0]
print(cs)
print(ms)

복잡도

• 시간: O(R x N) — 라운드 수 x 친구 수만큼 비교
• 공간: O(N) — 친구들의 선택 문자열 저장