[Python] 19778번 Игра

 

 

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

---

 

24/05/20

 

 

그룹 연습 문제로 풀었던 문제다.

 

간단한 게임 이론 + 구현 문제다. 최적의 전략을 생각하는 것이 그다지 어렵지는 않지만, 이를 실제로 구현하는 것이 전략을 생각하는 난이도에 비해서 조금 까다로운 편이다.

 

골드 5에 비해 난이도가 낮다고 생각이 되어서 낮게 측정했다.

---

 

문제 접근 방식:

 

 

러시아어로 되어 있는 문제이기 때문에 번역을 하면 다음과 같이 번역할 수 있다.

 

문제 번역:
체육 수업 시간에 1학년 페티야와 바샤가 흥미로운 게임을 하고 있습니다. 남학생들 앞에 높이가 다른 $n$개의 기둥이 일렬로 서 있습니다. 남학생들은 $m$개의 반지를 가지고 번갈아 가며 기둥에 던지는데, 기둥에 이미 반지가 있으면 이 기둥에 반지를 던질 수 없습니다. Petya가 먼저 던집니다. 아이들은 페티아가 기둥의 높이가 $l_1$ 이상 $r_1$ 이하인 경우에만 기둥에 반지를 던질 수 있다는 것을 알아냈습니다. 너무 높거나 너무 낮은 기둥에는 반지를 던질 수 없습니다. 그러나 포스트의 높이가 적당하다면 던지기는 성공할 수 있습니다. 마찬가지로 Vasya는 높이가 $l_2$ 이상 $r_2$ 이하인 기둥에만 링을 던질 수 있으며 그러한 기둥에 링을 던지는 것이 보장됩니다. 체육 교사 안드레이 세르게예비치는 기둥에 더 많은 반지를 던지는 소년에게 A를 주겠다고 약속했습니다. 소년들이 최적의 게임에서 누가 이길지 알아낼 수 있도록 도와주세요.
입력 파일의 첫 번째 줄에는 각각 기둥과 고리의 수인 두 개의 정수 $n$과 $m$이 들어 있습니다($1 \leq m \leq n \leq 10^5$). 다음 두 줄에는 숫자 $l_1$, $r_1$과 $l_2$, $r_2$ --- 각각 Petya와 Vasya가 고리를 던질 수 있는 열의 최소 및 최대 높이가 포함됩니다($1 \leq l_1, r_1, l_2, r_2 \leq 10^9$). 마지막 줄에는 열의 높이를 나타내는 $n$개의 숫자가 포함되며, 각 열의 높이는 양의 정수이며 $10^9$를 초과하지 않습니다.

 

최적의 전략은 너무 쉽게 생각할 수 있다.

 

Petya와 Vasya가 모두 놓을 수 있는 막대에 먼저 고리를 넣는 것이다. 이후 자신만 넣을 수 있는 막대에 고리를 넣으면 된다.

 

중국집을 가면, 많이 먹는 친구들을 관찰해보면, 짜장면이랑 짬뽕은 먼저 안먹고 탕수육 먼저 먹는 걸 볼 수 있는데, 탕수육은 공용으로 먹는 것이기 때문에 빨리 먹어야 하고, 짜장면이랑 짬뽕은 개인의 것이기 때문에 나중에 언제든지 먹을 수 있기 때문이다.

 

여기도 똑같다.

 

이를 그대로 구현하는 것이 이 문제의 관건이라고 할 수 있다.

 

구현 상의 편의를 위해 두 명이 던진 고리의 수가 주어지면 누가 이길지를 출력하는 함수 Compare를 구현했다.(중복된 코드여서)

 

그리고 각 기둥 별로, Petya"만" 던질 수 있는 기둥, Vasya"만" 던질 수 있는 기둥, 둘 모두 던질 수 있는 기둥의 개수를 각각 세주었다.

 

둘 모두 던질 수 있는 기둥의 개수를 편의 상 $K$라고 하겠다.

 

만약 $K \geq M$이라면, 서로 둘 모두 던질 수 있는 기둥에만 던지다가 고리를 모두 소모할 것이다.

 

Petya가 선공이므로, Petya가 던진 고리의 개수는 $(M+1)//2$개이고, Vasya가 던진 고리의 개수는 $M//2$개이다.

 

만약 $K < M$이라면, 고리가 다 소모되기 전에 둘 모두 던질 수 있는 기둥이 없어질 것이다.

 

따라서, 남은 고리를 갱신해주고, Petya가 던졌던 고리의 개수, Vasya가 던진 고리의 개수를 갱신해주었다.

 

Petya가 던졌던 고리의 개수는 $(K+1)//2$개이고, Vasya가 던졌던 고리의 개수는 $K//2$개이다.

 

만약 두 사람이 던졌던 고리의 개수가 같았다면, 이후의 턴은 Petya부터 시작한다.(Petya가 선공이 된다.)

그게 아니라면 이후의 턴은 Vasya부터 시작한다.(Vasya가 선공이 된다.)

 

각자가 던질 수 있는 고리와 각자가 던질 수 있는 기둥 중 최솟값이, 각자가 실제로 던진 고리일 것이다.

 

따라서 이를 통해 Petya와 Vasya가 던졌던 고리를 새롭게 갱신해주었다.

 

자세한 내용은 코드를 참고하면 확인할 수 있다.

---

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

# 19778번 Игра
# 게임 이론, 많은 조건 분기
'''
문제 번역:
체육 수업 시간에 1학년 페티야와 바샤가 흥미로운 게임을 하고 있습니다.
남학생들 앞에 높이가 다른 $n$개의 기둥이 일렬로 서 있습니다.
남학생들은 $m$개의 반지를 가지고 번갈아 가며 기둥에 던지는데,
기둥에 이미 반지가 있으면 이 기둥에 반지를 던질 수 없습니다.
페트야가 먼저 던집니다.
아이들은 페티아가 기둥의 높이가 $l_1$ 이상 $r_1$ 이하인 경우에만
기둥에 반지를 던질 수 있다는 것을 알아냈습니다.
너무 높거나 너무 낮은 기둥에는 반지를 던질 수 없습니다.
그러나 포스트의 높이가 적당하다면 던지기는 성공할 수 있습니다.
마찬가지로 Vasya는 높이가 $l_2$ 이상 $r_2$ 이하인 기둥에만 링을 던질 수 있으며
그러한 기둥에 링을 던지는 것이 보장됩니다.
체육 교사 안드레이 세르게예비치는 기둥에 더 많은 반지를 던지는 소년에게
“A”를 주겠다고 약속했습니다.
소년들이 최적의 게임에서 누가 이길지 알아낼 수 있도록 도와주세요.

입력 파일의 첫 번째 줄에는 각각 기둥과 고리의 수인 두 개의 정수 $n$과 $m$이 들어 있습니다($1 \le m \le n \le 10^5$).
다음 두 줄에는 숫자 $l_1$, $r_1$과 $l_2$, $r_2$ --- 각각 Petya와 Vasya가 고리를 던질 수 있는 열의 최소 및 최대 높이가 포함됩니다($1 \le l_1, r_1, l_2, r_2 \le 10^9$).
마지막 줄에는 열의 높이를 나타내는 $n$ 숫자가 포함되며, 각 열의 높이는 양의 정수이며 10^9를 초과하지 않습니다.

접근 방법:
'자신'만 던질 수 있고 상대방이 던질 수 있는 기둥에는 최대한 늦게 던진다.
둘 모두 던질 수 있는 기둥에 먼저 던지도록 한다.
'''
import sys
input = sys.stdin.readline

def compare(Pring, Vring):
    if Pring > Vring: print('Petya')
    elif Pring == Vring: print('Draw')
    else: print('Vasya')
    return

def solve():
    N, M = map(int, input().split())  # 기둥과 고리의 수, 고리는 합계로 계산...
    L1, R1 = map(int, input().split())
    L2, R2 = map(int, input().split())
    pillars = list(map(int, input().split()))
    Petya_throw, Vasya_throw = 0, 0
    Petya_only, Vasya_only, Both_ok = 0, 0, 0
    for height in pillars:
        if L1 <= height <= R1 and not (L2 <= height <= R2):
            Petya_only += 1
        elif L2 <= height <= R2 and not (L1 <= height <= R1):
            Vasya_only += 1
        elif L1 <= height <= R1 and L2 <= height <= R2:
            Both_ok += 1
    if Both_ok >= M:  # 둘 다 던질 수 있는 곳이 M보다 크거나 같은 경우
        Petya_throw, Vasya_throw = (M+1)//2, M//2
        compare(Petya_throw, Vasya_throw)
        return
    Petya_throw += (Both_ok + 1)//2
    Vasya_throw += Both_ok // 2
    M -= Both_ok  # 남은 고리의 개수 갱신
    if Petya_throw == Vasya_throw:
        Petya_can_throw, Vasya_can_throw = (M+1)//2, M//2
        Petya_throw += min(Petya_can_throw, Petya_only)
        Vasya_throw += min(Vasya_can_throw, Vasya_only)
        compare(Petya_throw, Vasya_throw)
        return
    else:
        Petya_can_throw, Vasya_can_throw = M//2, (M+1)//2
        Petya_throw += min(Petya_can_throw, Petya_only)
        Vasya_throw += min(Vasya_can_throw, Vasya_only)
        compare(Petya_throw, Vasya_throw)
        return
solve()