Educational Codeforces Round 88 (Rated for Div. 2) A - Berland Poker 풀이

Educational Codeforces Round 88 (Rated for Div. 2) A - Berland Poker 코드포스 A 풀이

codeforces.com/contest/1359/problem/A

Problem - A - Codeforces

---

문제 설명

정해진 룰에 따라 카드 게임을 한다. 총 카드의 수 n 조커카드의 수 m 게임하는 인원수 k 즉, 한 사람당 소지할 수 있는 최대 카드의 수는 n/k가 된다. 조커 카드를 가장 많이 갖고 있는 사람의 조커 카드 수와 두번째로 많이 갖고 있는 사람의 조커 카드 수를 빼준다. 이 조건을 만족했을때 최대 값은 몇인가?

---

문제 풀이

문제를 이해 했다면, 첫번째 사람이 가져갈 수 있는 조커 카드의 최대 수(x라는 변수)를 먼저 계산해야 한다는 것을 알 것이다. 1. 조커 카드의 총 갯수(m)가 한 사람이 가져가는 카드 수(n/k)보다 큰 경우엔 한 사람이 가져가는 카드 수만큼 가져간다. 2. 조커 카드의 총 갯수(m)가 한 사람이 가져가는 카드 수(n/k)보다 적은 경우엔 조커 카드의 총 갯수만큼 가져간다. 코드로 표현한다면 아래와 같다. if m>n/k:    x = n/k else:    x = m 위의 연산을 했다면 이제 남은 조커 카드의 총 갯수와 남은 인원의 수를 구하자. 남은 조커 카드의 갯수 : m-x 전체 조커 카드의 수에서 첫번째 사람이 가져간 조커 카드의 수만큼 빼주면 된다. 남은 인원의 수 : k-1 첫번째 사람은 연산이 끝났으니까 전체 인원에서 1을 빼주는 것이다. 자, 끝났다. 남은 사람들은 조커 카드를 남은 조커 카드의 수 / 남은 인원의 수만큼 가져간다.(전체 카드의 수/총 인원과 같은 개념) 하지만, Example의 9 6 3과 같은 예제는 정확히 나누어 떨어지지 않는다. 즉, 위와 같이 연산하면 소수의 결과가 나온다. 9 6 3 예제에서 첫번째 사람은 3 두번째 사람은 1 세번재 사람은 2 만큼의 조커 카드를 가져가는데 이는 단순히 우리가 했던 연산에서 올림을 해주면 된다. 이 값을 변수명 y라고 정한다. 정리하면, x = min(k/n, m) 첫번째 사람이 가져가는 조커 카드의 최대 수 y = ceil(m-x / k-1) 남은 사람중 조커 카드 수의 최대값 정답 : x-y

---

소스 코드

Python3

import sys
import math
input = sys.stdin.readline

t=int(input().strip())
while t:
    t-=1
    n,m,k=map(int,input().split())
    d = n // k  #한 사람당 가져가는 카드 수
    x = min(m, d)   #첫 번째 사람이 가져가는 카드의 수
    #if m>d: return d
    #else: return m
    #이렇게 써줘도 전혀 상관이 없다. 같은 방식인데 min으로하면 더 간단하다.

    y = math.ceil((m-x)/(k-1)) #남은 사람중 가져가는 카드의 최대 수
    print(x-y)