[백준 21760] 야구 시즌

야구 시즌 (21760)

문제 출처 : https://www.acmicpc.net/problem/21760

 

이 문제는 2021년 정보올림피아드 1차 고등부 1번 문제 입니다.

N개의 리그가 존재하고, 각 리그에는 M개의 팀이 있습니다. 모든 리그에 팀은 M개로 정해져 있는지 리그 전체의 팀은 N * M 개 입니다.

같은 리그에서는 같은 리그에 있는 다른 팀과 각각 A번 씩 경기를 해야 합니다. 그리고 다른 지역과는 B번 씩 경기를 해야 합니다. A와 B는 다음과 같은 관계를 가집니다.

A = k * B

판데믹의 영향으로 경기의 수를 D번으로 제한 하게 되었고, A, B 값을 조절해야 합니다. 하지만 모든 팀들은 한 번 이상 경기를 진행해야 합니다. 즉 A, B는 1 이상 입니다.

문제 이해하기

N, M, k, D가 주어졌을 때 경기의 최대값을 구하는 문제 입니다. 이런 문제가 주어지면 이분 탐색이 아닐까 하는 의심을 한 번 해봐야 합니다. 정확한 값을 찾기 어려울 때 비교를 해가며 답을 찾아야 하는 경우 대부분 이분 탐색을 사용합니다.

우리가 알아야 할 공식이 하나 있습니다. 바로 M개의 팀이 과연 몇개의 경기를 진행하는지 알아야 합니다. 이것은 조합의 공식을 사용하면 알 수 있습니다. 조합을 구하는 공식은 아래 링크를 통해 알 수 있습니다.

https://wikidocs.net/206248#_4

05. 브루트 포스

 

위 공식을 통해 각 리그에 M개의 팀이 치루는 경기의 개수는 아래와 같습니다.

한 팀당 리그 경기 조합 수 = M * (M - 1) / 2

공식을 통해 구한 조합 수에 A를 곱하면 한 지역에서 몇 번의 경기를 진행하는지 알 수 있습니다. 여기에 리그의 개수 N을 곱하면 전체 리그의 경기 수를 알 수 있습니다.

한 지역 당 같은 리그 경기 수 = A * (M * (M - 1) / 2)

전체 지역 같은 리그 경기 수 = N * A * (M * (M - 1) / 2)

이제 다른 지역과의 경기수를 알아보겠습니다. 다른 지역과의 경기 역시 조합 공식을 사용합니다. 다른 지역의 개수는 N개이고 N개의 리그 팀과 경기를 치룹니다. 여기에 한 팀당 치루어야 할 경기수인 B를 곱해주어야 합니다. 여기에 각 리그의 개수 M을 곱해주어야 합니다.

한 팀당 다른 리그와의 경기 조합 수 = B * (N * (N - 1) / 2)

한 팀이 치루어야 할 경기 조합 수에 전체 리그 수를 곱해주어야 합니다. 한 리그 당 M개의 팀이 있고, 리그 당 M개의 팀이 경기를 치루기 때문에 M을 두 번 곱해주어야 합니다.

전체 다른 리그와의 경기 수 = M * M * B * (N * (N - 1) / 2)

예제를 보면 N = 2, M = 3, k = 3, D = 60 입니다. 우리가 찾아야 할 값은 B 입니다. B 값을 알면 A를 알 수 있고, 전체 경기 수를 알 수 있습니다. B 값을 이분 탐색으로 조절해 가며 전제 경기수를 찾아 보겠습니다. 먼저 B 가 1인 경우 입니다.

그럼 위 공식을 통해 전체 지역 리그의 총 경기 수를 구할 수 있습니다. 원래 이분 탐색의 경우 최대값부터 반 씩 줄여나가서 계산하는 것이 맞지만 여기서는 B값을 3부터 해보겠습니다. 너무 많은 계산이 나올 것 같기 때문입니다.

A = k * B = 3 * 3 = 9

전체 지역 같은 리그 경기 수 = N * A * (M * (M - 1) / 2) = 2 * 9 * 3 * 2 / 2 = 54

전체 다른 리그와의 경기 수 = M * M * B * (N * (N - 1) / 2) = 3 * 3 * 3 * 2 * 1 / 2 = 27

전체 경기 수 = 54 + 27 = 81

전체 경기수 D 가 60이기 때문에 81 경기는 너무 많습니다. B값을 줄여 주어야 합니다. 3 /// 2 = 1이기 때문에 B값을 1로 하여 계산해 보겠습니다.

A = k * B = 3 * 1 = 3

전체 지역 같은 리그 경기 수 = N * A * (M * (M - 1) / 2) = 2 * 3 * 3 * 2 / 2 = 18

전체 다른 리그와의 경기 수 = M * M * B * (N * (N - 1) / 2) = 3 * 3 * 1 * 2 * 1 / 2 = 9

전체 경기 수 = 27

두 계산 결과의 합은 27로 D값인 60에 비해 너무 작습니다. 3과 1 사이의 2로 계산해 보겠습니다.

A = k * B = 3 * 2 = 6

전체 지역 같은 리그 경기 수 = N * A * (M * (M - 1) / 2) = 2 * 6 * 3 * 2 / 2 = 36

전체 다른 리그와의 경기 수 = M * M * B * (N * (N - 1) / 2) = 3 * 3 * 2 * 2 * 1 / 2 = 18

전체 경기 수 = 54

이제 원하는 결과가 나왔습니다. D값 60 보다 작습니다. B 값이 3인 경우는 범위를 벗어난다는 사실을 알고 있습니다. 즉 우리가 찾던 결과는 B값이 2인 경우 전체 경기수 54입니다. 이렇게 54를 출력해 주면 됩니다.

코드 작성하기

그럼 지금 배운 것으로 코드를 작성해 보겠습니다.

입력 받기

T = int(input())

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

전체 테스트 케이스의 수 T를 입력 받습니다. 다음으로 테스트 케이스의 수 만큼 계산해야 할 숫자들을 받습니다. 리그의 수 N, 리그 당 팀의 수 M, A와 B를 계산할 수 있는 k값, 마지막으로 전체 경기수 D를 입력 받습니다. 입력을 모두 받으면 이분 탐색을 통해 결과를 얻습니다.

이분 탐색 로직 구현

def binary_search():
    start, end = 1, D
    ans = -1
    while start <= end:
        B = (start + end) // 2
        total_game = solve(B)
        if total_game <= D:
            ans = max(ans, total_game)
            start = B + 1
        else:
            end = B - 1

    print(ans)

이분 탐색 로직 입니다. 이분 탐색에 대한 설명은 아래 링크로 대신하겠습니다.

https://wikidocs.net/206313

05. 이분 탐색

 

모든 경기는 최소 1번 이상 이루어지기 때문에 start 값은 1입니다. 그리고 최대 경기수 D를 넘을 수 없기 때문에 end값은 D로 초기화 하였습니다. 다음으로 보통 mid로 변수명을 사용하지만 여기서는 우리가 찾고 있는 B로 변수명을 정했습니다. 결과가 없는 경우 -1을 출력하기 위해 ans값의 초기값은 -1 입니다. solve 함수를 통해 총 경기수를 계산합니다. 계산된 결과는 D값과 비교하면서 start와 end값을 조절합니다.

solve 함수

def solve(B):
    A = k * B
    ans1 = N * ((M * (M - 1)) // 2) * A
    ans2 = M * M * (N * (N - 1) // 2) * B
    return ans1 + ans2

입력받은 B를 통해 A를 구하고 최종적으로 전체 경기수를 구하는 로직 입니다. 로직의 설명은 위에서 이미 서술하였기 때문에 따로 자세한 설명은 하지 않겠습니다.

전체 코드

그럼 전체 코드를 알아보겠습니다.

def solve(B):
    A = k * B
    ans1 = N * ((M * (M - 1)) // 2) * A
    ans2 = M * M * (N * (N - 1) // 2) * B
    return ans1 + ans2

def binary_search():
    start, end = 1, D
    ans = -1
    while start <= end:
        B = (start + end) // 2
        total_game = solve(B)
        if total_game <= D:
            ans = max(ans, total_game)
            start = B + 1
        else:
            end = B - 1

    print(ans)

T = int(input())

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

수학으로 풀기

이분 탐색을 통해 답을 구하였는데 잘 생각해보면 모든 변수를 알고 있기 때문에 그냥 수학적으로도 충분히 구할 수 있어 보입니다.

A = k * B 입니다. 그리고 나머지는 모든 항목의 값을 알고 있습니다. 그럼 전체를 B로 묶을 수 있습니다.

ans1 = N * ((M * (M - 1)) // 2) * k ans2 = M * M * (N * (N - 1) // 2)

ans1에 A 대신 k를 곱해주고, ans2에는 B를 곱해주지 않았습니다. 그럼 전체 경기는 다음과 같이 됩니다.

total_game = (ans1 + ans2) * B

결국 total_game은 D에 근접한 어떤 값입니다. 즉 (ans1 + ans2) 값으로 나누어 보면 B를 구할 수 있게 됩니다.

temp = ans1 + ans2 B = D // temp

이 B 값이 0이라면 답이 없는 것이고, 어떤 값이 존재한다면 그 값이 우리가 찾던 B값이 됩니다. 최종적으로 B값을 출력하는 것이 아니라 전체 경기수를 출력하는 것이기 때문에 temp값을 곱해주면 전체 경기수를 알 수 있습니다.

수학으로 작성한 코드

def solve():
    ans1 = N * ((M * (M - 1)) // 2) * k
    ans2 = M * M * (N * (N - 1) // 2)
    temp = ans1 + ans2
    B = D // temp
	
    if B == 0:
        return -1
    else:
        return B * temp

T = int(input())

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