[Python] 백준/BOJ 21760번: 야구 시즌 (Silver 5)

💻 Problem

문제 보러 가기

 

KOI 야구 리그에는 N개의 지역리그가 존재하고 각 지역리그에는 M개의 팀이 존재해서, 리그 전체로는 N × M개의 팀으로 운영되고 있다.

한 시즌에 각 팀은 같은 지역리그 팀뿐만 아니라 다른 지역리그 팀과도 경기를 해야 한다. 같은 지역리그 팀과의 팀당 경기 수는 A로 같은 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 같은 지역리그에 있는 모든 팀 Y (≠ X)와 각각 A번의 경기를 한다. 또한 다른 지역리그 팀과의 팀당 경기 수는 B로 다른 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 다른 지역리그에 있는 모든 팀 Z( ≠  X)와 각각 B번의 경기를 한다. 단, A와 B는 A = k × B (k는 1 이상의 정수)를 만족해야 한다.

세계적 판데믹의 영향으로 올해 KOI 야구 리그는 시즌을 단축하여, 리그의 전체 경기 수가 D개 이하 이면서 D에 가장 가깝게 되도록 정하기로 했다. 따라서 같은 지역리그 팀과의 팀당 경기 수 A와 다른 지역리그 팀과의 팀당 경기 수 B를 새롭게 결정해야 한다. 물론, A = k × B를 만족해야 하고, k는 변함없이 유지되어야 한다. 또한 각 팀은 다른 팀과 적어도 한 번 이상은 경기를 해야 한다. 다시 말해서, A ≥ 1, B  ≥ 1을 만족해야 한다.

예를 들어, N = 2, M = 3, k = 3일 때, 경기 수 제한 D = 60이면, A = 6, B = 2일 때, 다른 지역리그 팀들과의 총 경기 수는 18이고, 같은 지역리그 팀들과의 총 경기 수는 36이다. 따라서 리그 전체 경기 수는 54로 D에 가장 가까운 새로운 경기 수이다.

지역리그의 개수 N, 각 지역리그에 속하는 팀 수 M, 그리고 위에서 A = k × B를 만족하는 정수 k, 새로운 경기 수 제한 D가 주어질 때, D 이하이면서 D에 가장 가까운 리그 전체 경기 수를 계산해서 출력하는 프로그램을 작성하시오.

 

💡 Approach

문제에서 나온 정보는 아래와 같다.

• N: 지역리그 수
• M: 한 지역리그당 팀 수
• A: 같은 지역리그 팀과의 팀당 경기 수
• B: 다른 지역리그 팀과의 팀당 경기 수
• A = k × B
• 리그 전체 경기수가 D 이하이면서 D에 가장 가까운 수
• 각 팀은 다른 팀과 적어도 한 번 이상은 경기를 해야 함

 

같은 지역리그 팀들과의 총 경기 수와 다른 지역리그 팀들과의 총 경기 수를 구해보자.

• same: 같은 지역리그 팀들과의 총 경기 수
  • 지역리그는 N개가 있고 한 지역리그 내에서 두 팀을 뽑아서 경기를 하므로 C(M, 2)이다. (C=조합)
  • N * C(M, 2) = N * (M * (M - 1) // 2)
• other: 다른 지역리그 팀들과의 총 경기 수
  • 여러 지역리그 중에 두 개의 지역리그를 뽑아 각 지역리그의 M개의 팀이 서로 경기한다.
  • C(N, 2) * M * M = (N * (N - 1) // 2) * M * M

same과 other 값을 구했으면 same * A + other * B가 리그 전체 경기 수이다.

A = k * B로 치환하면 same * k * B + other * B가 되고

B로 묶으면 B * (same * k + other)가 된다.

여기서 same * k + other = C라고 하겠다.

 

경기수 제한인 D에 C를 나누면 B의 값을 구할 수 있다.

정답은 리그 전체 경기 수이니 B에 C를 곱해서 출력한다.

 

✏️ Solution

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, M, k, D = map(int, input().split())

    same = N * (M * (M - 1) // 2)
    other = (N * (N - 1) // 2) * M * M
    C = same * k + other
    B = D // C

    print(-1 if B < 1 else B * C)

• 시간복잡도: O(1)