BOJ 3758번: KCPC

www.acmicpc.net/problem/3758

3758번: KCPC

아이디어: #정렬

1. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 
2. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다.

따라서 정렬 조건은 1. 최종점수 2. 풀이를 제출한 횟수 3. 마지막 제출 시간 이다.

최종 점수는 각 문제에 대해 받은 점수의 총합이고, 한 문제에 대한 풀이를 여러번 제출할 수 있으며 그 중 최고 점수가 그 문제의 최종 점수이다. 

입력 받을 때 팀ID, 문제번호, 획득 점수를 받으므로 배열을 만들어 저장할 수 있다. 인덱스를 팀 ID-1라고 하고 각 인덱스마다 [ID, score1, score2, score3, ... , scorek, sum(최종점수) num(제출횟수), time(제출시간)]을 가지게 한다.

arr = [[0]*(k+4) for _ in range(n)]

그리고 m개의 입력을 받으면서 제출시간을 계속 업데이트하고, 문제번호에 해당하는 인덱스에 최댓값을 업데이트하고, 그때마다 최종점수도 업데이트한다 최종점수는 맨 마지막에 계산한다. 제출횟수도 +1씩 계속 업데이트한다.

 

우선순위에 맞게 정렬을 하고, 내 팀 ID를 찾아서 순위를 출력한다.

 

코드:

#정렬

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    #팀의 개수, 문제의 개수, ID, 로그 엔트리 개수
    n, k, t, m = map(int, sys.stdin.readline().split())
    #arr[i] = [ID, score1, ..., scorek,최종점수, 제출횟수, 제출시간]
    arr = [[0]*(k+4) for _ in range(n)]

    #팀 ID
    for i in range(n):
        arr[i][0] = i+1
    
    for time in range(m):
        #ID, 문제 번호, 획득 점수
        i, j, s = map(int, sys.stdin.readline().split())
        arr[i-1][j] = max(arr[i-1][j], s) #문제별 최고점수
        arr[i-1][k+2]+=1 #제출횟수
        arr[i-1][k+3] = time #마지막 제출 시간

    for i in range(n):
        for j in range(1,k+1):
            arr[i][k+1] += arr[i][j] #최종점수 계산
    
    #정렬
    ans = sorted(arr, key = lambda x: (-x[k+1], x[k+2], x[k+3]))
    
    #내 팀 찾기
    for i in range(n):
        if (ans[i][0]==t):
            print(i+1)
            break
    

- 변수 중복문제.. 로 한 번 틀렸었다.

- 원래 팀 ID는 포함을 안 시켰다가 정렬 후에 팀 ID를 알 방법이 없다는 걸 뒤늦게 깨닫고.. 추가했다.