Python 77제] 2021년 한국정보올림피아드 1차대회 2교시 고등부 1번 야구 시즌

출처 : 반크_세계유산 석굴암

 

문제]

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

한 시즌에 각 팀은 같은 지역리그 팀뿐만 아니라 다른 지역리그 팀과도 경기를 해야 한다. 같은 지역리그 팀과의 팀당 경기 수는 A로 같은 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 같은 지역리그에 있는 모든 팀 Y (6= X)와 각각 A번의 경기를 한다. 또한 다른 지역리그 팀과의 팀당 경기 수는 B로 다른 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 다른 지역리그에 있는 모든 팀 Z(6= 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에 가장 가까운 리그 전체 경기 수를 계산해서 출력하는 프로그램을 작성하시오.

제약 조건)
• 주어지는 모든 수는 정수이다.
• 하나의 입력 데이터에서 1개 이상 1 000개 이하의 테스트 케이스를 해결해야 한다.
• 2 ≤ N, M ≤ 100
• 1 ≤ k ≤ 100
• 1 ≤ D ≤ 1,000,000,000

입력 형식)
첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.
다음 T개의 줄에 각 테스트 케이스의 정보가 한 줄에 하나씩 주어진다.
각 테스트 케이스는 하나의 줄에 네 개의 정수 N, M, k, D가 공백 하나를 사이로 두고 주어진다.

출력 형식)
T개의 각 줄에 각 테스트 케이스에 대해 리그 전체 경기 수를 출력한다.
만약 조건을 만족하는 경기 수가 존재하지 않으면 -1을 출력한다.

 

예제 입력)

3

2 3 3 60

2 2 1 18

2 2 1 4

 

예제 출력)

54

18

-1

 

 

출처 : 2021년 한국정보올림피아드 1차대회 2교시 고등부 1번

 

참고풀이]

import sys #exit()

#T값을 입력한다.
T=int(input())
if 1<=T<=1000: #1<=T<=1000 조건에 맞으면 작업을 계속한다.
    L=[]
    #T회의 자료를 입력받는다.
    for i in range(T):
        In=list(map(int, input().split(' ')))
        if 2<=In[0]<=100: #2<=N<=100 조건에 맞고
            if 2<=In[1]<=100: #2<=M<=100 조건에 맞고
                if 1<=In[2]<=100: #2<=k<=100 조건에 맞고
                    if 1<=In[3]<=1000000000: #1<=D<=1000000000 조건에 맞으면 
                        L.append(In) #처리할 자료에 넣는다.
                    else:
                        sys.exit()
                else:
                    sys.exit()
            else:
                sys.exit()
        else:
            sys.exit()
else:
    sys.exit()

#입력된 경기수의 근사값을 구한다.    
for In in L:
    B=int(2*In[3]/(In[0]*In[1]*(In[2]*(In[1]-1)+(In[0]-1)*In[1])))
    if B<0:
        print(-1)
    else:
        print(In[0]*In[1]*(In[2]*(In[1]-1)+(In[0]-1)*In[1])*B//2)

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 겨울