문제 링크
문제 요약
두 명의 플레이어 Vilius와 Adomas가 가위바위보 게임을 합니다. 각 플레이어는 가위, 바위, 보를 몇 번 냈는지 총 횟수는 알지만, 어떤 순서로 냈는지는 기억하지 못합니다.
이기면 +1점, 지면 -1점, 비기면 0점입니다.
주어진 가위, 바위, 보 횟수를 바탕으로 Vilius가 얻을 수 있는 최대 점수와 최소 점수를 계산해야 합니다.
풀이
이 문제는 주어진 가위, 바위, 보의 총 횟수만 중요하고, 어떤 순서로 냈는지는 중요하지 않다는 점을 이용한 그리디(Greedy) 문제입니다. Vilius의 점수를 최대로 만들거나 최소로 만드는 두 가지 시나리오를 각각 고려하여 풀이할 수 있습니다.
Vilius의 점수를 최대로 만드는 경우: Vilius의 점수를 최대로 만들기 위해서는 Vilius가 이기는 경우(+1점)를 최대한 많이 발생시켜야 합니다. 그 다음으로는 점수에 영향을 주지 않는 비기는 경우(0점)를 처리하고, 마지막으로 점수를 잃는 지는 경우(-1점)를 최소화해야 합니다.
- Vilius가 이기는 경우를 우선 처리: Vilius의 각 손패(바위, 가위, 보)가 Adomas의 어떤 손패를 이길 수 있는지 확인하고, 가능한 최대 횟수만큼 Vilius가 이기도록 매칭합니다. 예를 들어, Vilius가 바위를 내고 Adomas가 가위를 냈다면 Vilius가 이깁니다. 이 매칭에 사용된 손패의 개수는 양쪽에서 차감합니다.
- 비기는 경우를 그 다음으로 처리: 남은 손패 중에서 Vilius와 Adomas가 동일한 손패를 낼 수 있다면, 이들을 비기는 것으로 매칭합니다. 비기는 경우는 점수 변화가 없으므로 최대 점수 계산에 영향을 주지 않습니다. 이 매칭에 사용된 손패의 개수는 양쪽에서 차감합니다.
- Vilius가 지는 경우를 마지막으로 처리: 1, 2단계를 거치고 남은 손패들은 모두 Vilius가 지는 경우로 이어집니다. 이 경우 Vilius의 점수가 감소하므로, 이를 마지막에 계산합니다.
Vilius의 점수를 최소로 만드는 경우: Vilius의 점수를 최소로 만들기 위해서는 Vilius가 지는 경우(-1점)를 최대한 많이 발생시켜야 합니다. 그 다음으로는 점수에 영향을 주지 않는 비기는 경우(0점)를 처리하고, 마지막으로 점수를 얻는 이기는 경우(+1점)를 최소화해야 합니다.
- Vilius가 지는 경우를 우선 처리: Vilius의 각 손패가 Adomas의 어떤 손패에 질 수 있는지 확인하고, 가능한 최대 횟수만큼 Vilius가 지도록 매칭합니다. 예를 들어, Vilius가 바위를 내고 Adomas가 보를 냈다면 Vilius가 집니다. 이 매칭에 사용된 손패의 개수는 양쪽에서 차감합니다.
- 비기는 경우를 그 다음으로 처리: 위와 동일하게, 남은 손패 중 동일한 손패를 낼 수 있다면 비기는 것으로 매칭합니다.
- Vilius가 이기는 경우를 마지막으로 처리: 1, 2단계를 거치고 남은 손패들은 모두 Vilius가 이기는 경우로 이어집니다. 이 경우 Vilius의 점수가 증가하므로, 이를 마지막에 계산합니다.
위 두 가지 전략을 각각 사용하여 최대 점수와 최소 점수를 구하면 됩니다. 코드는 이 과정을 greedy_win (최대 점수) 및 greedy_lose (최소 점수) 함수로 구현하며, 각 함수 내에서 win, tie, lose 헬퍼 함수를 호출하여 특정 유형의 매칭을 처리합니다. 이때 win, tie, lose 함수는 주어진 리스트를 직접 변경하므로, greedy_win과 greedy_lose를 호출할 때 입력 리스트의 복사본을 넘겨주어야 독립적인 계산이 가능합니다 (A[::], B[::]).
가위, 바위, 보를 인덱스로 표현하면 0: 바위, 1: 보, 2: 가위와 같이 표현할 수 있습니다.
- Vilius(
a[i])가 이기는 경우:a[i]는b[(i+2)%3]를 이깁니다. (예: 바위(0)는 가위(2)를 이김, 보(1)는 바위(0)를 이김, 가위(2)는 보(1)를 이김) - Vilius(
a[i])가 지는 경우:a[i]는b[(i+1)%3]에 집니다. (예: 바위(0)는 보(1)에 짐, 보(1)는 가위(2)에 짐, 가위(2)는 바위(0)에 짐)
정답 코드
"""
[7213: Akmuo, popierius, žirklės](https://www.acmicpc.net/problem/7213)
Tier: Bronze 1
Category: greedy, implementation
"""
import sys
from math import sqrt, pi, sin, factorial, ceil, floor
from datetime import datetime, timedelta
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, product
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
from operator import itemgetter, attrgetter, mul, add, sub, truediv
from typing import List, Tuple, Dict, Set, Any, Union
SYS_INPUT = True
RECURSION_LIMIT = 10 ** 7
SET_RECURSION = False
BLANK = " "
if SET_RECURSION:
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda : sys.stdin.readline().rstrip() if SYS_INPUT else input()
mii = lambda : [*map(int,inp().split())]
mfi = lambda : [*map(float,inp().split())]
ii = lambda : int(inp())
fi = lambda : float(inp())
isplit = lambda : inp().split()
p = print
def gcd(a, b): return gcd(b, a % b) if b > 0 else a
def lcm(a, b): return a * b // gcd(a, b)
def win(a, b):
ret = 0
for i in range(3):
# a[i] (Vilius의 현재 손패)로 b[(i + 2) % 3] (Adomas의 지는 손패)를 이김
# 0: 바위, 1: 보, 2: 가위
# 바위(0)는 가위(2)를 이김 (0 vs (0+2)%3 = 2)
# 보(1)는 바위(0)를 이김 (1 vs (1+2)%3 = 0)
# 가위(2)는 보(1)를 이김 (2 vs (2+2)%3 = 1)
k = min(a[i], b[(i + 2) % 3])
a[i] -= k
b[(i + 2) % 3] -= k
ret += k
return ret
def tie(a, b):
for i in range(3):
# a[i] (Vilius의 현재 손패)와 b[i] (Adomas의 동일 손패)가 비김
k = min(a[i], b[i])
a[i] -= k
b[i] -= k
def lose(a, b):
ret = 0
for i in range(3):
# a[i] (Vilius의 현재 손패)로 b[(i + 1) % 3] (Adomas의 이기는 손패)에 짐
# 바위(0)는 보(1)에 짐 (0 vs (0+1)%3 = 1)
# 보(1)는 가위(2)에 짐 (1 vs (1+1)%3 = 2)
# 가위(2)는 바위(0)에 짐 (2 vs (2+1)%3 = 0)
k = min(a[i], b[(i + 1) % 3])
a[i] -= k
b[(i + 1) % 3] -= k
ret -= k
return ret
def greedy_win(a, b):
# Vilius가 이기는 경우를 최대로, 지는 경우를 최소로
ret = 0
ret += win(a, b) # Vilius가 이김
tie(a, b) # 비김 (점수 영향 없음)
ret += lose(a, b) # Vilius가 짐
return ret
def greedy_lose(a, b):
# Vilius가 지는 경우를 최대로, 이기는 경우를 최소로
ret = 0
ret += lose(a, b) # Vilius가 짐
tie(a, b) # 비김 (점수 영향 없음)
ret += win(a, b) # Vilius가 이김
return ret
def solve():
A = mii() # Vilius의 바위, 보, 가위 횟수 (0: 바위, 1: 보, 2: 가위)
B = mii() # Adomas의 바위, 보, 가위 횟수
# 최대 점수 계산 (A, B 리스트는 함수 내에서 변경되므로 복사본 전달)
max_score = greedy_win(A[::], B[::])
# 최소 점수 계산 (A, B 리스트는 함수 내에서 변경되므로 복사본 전달)
min_score = greedy_lose(A[::], B[::])
print(max_score)
print(min_score)
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()