문제
당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다. 풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.)
당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다.
점수가 동일한 팀이 여럿 있을 수 있는데, 그 경우에는 다음 규칙에 의해서 순위가 정해진다.
- 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다.
- 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다.
동시에 제출되는 풀이는 없고, 모든 팀이 적어도 한 번은 풀이를 제출한다고 가정하라.
서버의 로그가 주어졌을 때, 당신 팀의 순위를 계산하는 프로그램을 작성하시오.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 팀의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m을 나타내는 4 개의 정수가 주어진다. 여기서, 3 ≤ n, k ≤ 100, 1 ≤ t ≤ n, 3 ≤ m ≤ 10,000이다. 그 다음 m개의 줄에는 각 풀이에 대한 정보가 제출되는 순서대로 주어진다. 각 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 주어진다. 여기서 1 ≤ i ≤ n, 1 ≤ j ≤ k, 0 ≤ s ≤ 100이다.
출력
출력은 표준출력을 사용한다. 주어진 각 테스트 데이터에 대해 당신 팀의 순위를 한 줄에 출력하여야 한다
예제 입력 1
2
3 4 3 5
1 1 30
2 3 30
1 2 40
1 2 20
3 1 70
4 4 1 10
1 1 50
2 1 20
1 1 80
3 1 0
1 2 20
2 2 10
4 3 0
2 1 0
2 2 100
1 4 20
예제 출력 1
1
2
아이디어
문제에 대한 이해는 엄청 간단했다. 하라는대로만 하면 되는…
근데 전체적으로 짜다보면 되게 복잡할 것 같다.
그래서 중첩리스트를 이용하기로 했다.
중첩리스트에 각 팀 별 시도횟수, 제출 시간, 문제별 점수를 담은 rankingBoard를 만들어서 비교할 수 있다.
문제 풀이
'''
백준 실버2 3758번
KCPC
'''
T = int(input()) # 테스트 데이터의 수를 나타내는 정수
for _ in range(T):
n, k, t, m = map(int, input().split()) # n: 팀의 개수, k: 문제의 개수, t: 당신 팀의 ID, m: 로그 엔트리의 개수
rankingBoard = [] # 각 팀 별 결과를 저장할 중첩리스트
# rankingBoard 초기화
for _ in range(n):
rankingBoard.append([0, 0, [0 for _ in range(k)]]) # 각 팀별 시도 횟수, 제출 시간, 문제 별 점수
for time in range(m):
i, j, s = map(int, input().split()) # i: 팀 ID, j: 문제 번호, s: 획득한 점수
rankingBoard[i-1][0] += 1 # 해당 팀의 제출 횟수 추가
rankingBoard[i-1][1] = time # 제출 시간 저장
rankingBoard[i-1][2][j-1] = max(s, rankingBoard[i-1][2][j-1]) # 문제 j의 점수 저장(최고 점수 기준)
# 최종 점수 합산
sumScore = [0] * n
for id in range(n):
sumScore[id] = sum(rankingBoard[id][2])
# 등수 계산
my = 1
for team in range(n):
if team+1 == t:
continue
else:
if sumScore[team] > sumScore[t-1]:# 더 높은 점수를 가지는 팀이 존재하는 경우
my += 1
elif sumScore[team] == sumScore[t-1]: # 최종 점수가 같을 경우
if rankingBoard[team][0] < rankingBoard[t-1][0]: # 우리 팀의 제출 횟수가 더 많으면, 순위가 내려감
my += 1
elif rankingBoard[team][0] == rankingBoard[t-1][0]: # 제출횟수가 같은 경우,
if rankingBoard[team][1] < rankingBoard[t-1][1]: # 마지막 제출 시간이 더 빠른 팀이 이김
my += 1
print(my)
인덱스 번호만 헷갈리지 않으면 구현은 어렵지 않은 문제이다.
'코딩테스트 > 백준(Python)' 카테고리의 다른 글
[백준][Python] 21921번. 블로그 (실버3) (0) | 2024.07.11 |
---|---|
[백준][Python] 13549번. 숨바꼭질3 (0) | 2024.07.10 |
[백준][Python] 20922번. 겹치는 건 싫어(실버1) (0) | 2024.07.06 |
[백준][Python] 15989번 1, 2, 3 더하기 4(골드5) (0) | 2024.07.06 |
[그리디][파이썬][백준] 13305번 주유소 (0) | 2023.03.30 |