백준 2461 [대표 선수] 파이썬

https://www.acmicpc.net/problem/2461

 

아 미치겠다.. 쉽지않다..

#백준 2461 대표
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
classes=[]
class_idx=[0 for _ in range(N)]
for _ in range(N):
    class_=list(map(int,input().split()))
    class_.sort()
    classes.append(class_)
ans=float('inf')
for i in range(M):
    std=classes[0][i]
    up_diff=0
    down_diff=0
    for j in range(1,N):
        idx=class_idx[j]
        while idx<M-1 and classes[j][idx]<std:
            idx+=1
        if 0<idx<M-1:
            prev=classes[j][idx-1]
            aft=classes[j][idx]
            if std-prev<aft-std:
                down_diff=max(down_diff,std-prev)
            else:
                up_diff=max(up_diff,aft-std)
        elif idx==0:
            if classes[j][idx]>std:
                up_diff=max(up_diff,classes[j][idx]-std)
            else:
                down_diff=max(down_diff,std-classes[j][idx])
        else:
            if classes[j][idx]>std:
                prev=classes[j][idx-1]
                aft=classes[j][idx]
                if std-prev<aft-std:
                    down_diff=max(down_diff,std-prev)
                else:
                    up_diff=max(up_diff,aft-std)
            else:
                down_diff=max(down_diff,std-classes[j][idx])

        class_idx[j]=idx
    
    if up_diff>=down_diff:
        down_diff=0
        for j in range(1,N):
            idx=class_idx[j]
            if 0<idx<M-1:
                prev=classes[j][idx-1]
                aft=classes[j][idx]
                p_diff=std-prev
                a_diff=aft-std
                if a_diff>up_diff:
                    down_diff=max(down_diff,p_diff)
            elif idx==0:
                if classes[j][idx]>std:
                    up_diff=max(up_diff,classes[j][idx]-std)
                else:
                    down_diff=max(down_diff,std-classes[j][idx])
            else:
                if classes[j][idx]>std:
                    prev=classes[j][idx-1]
                    aft=classes[j][idx]
                    p_diff=std-prev
                    a_diff=aft-std
                    if a_diff>up_diff:
                        down_diff=max(down_diff,p_diff)
                else:
                    down_diff=max(down_diff,std-classes[j][idx])
    elif up_diff<down_diff:
        up_diff=0
        for j in range(1,N):
            idx=class_idx[j]
            if 0<idx<M-1:
                prev=classes[j][idx-1]
                aft=classes[j][idx]
                p_diff=std-prev
                a_diff=aft-std
                if p_diff>down_diff:
                    up_diff=max(up_diff,a_diff)
            elif idx==0:
                if classes[j][idx]>std:
                    up_diff=max(up_diff,classes[j][idx]-std)
                else:
                    down_diff=max(down_diff,std-classes[j][idx])
            else:
                if classes[j][idx]>std:
                    prev=classes[j][idx-1]
                    aft=classes[j][idx]
                    p_diff=std-prev
                    a_diff=aft-std
                    if p_diff>down_diff:
                        up_diff=max(up_diff,a_diff)
                else:
                    down_diff=max(down_diff,std-classes[j][idx])
    ans=min(down_diff+up_diff,ans)

print(ans)

말도 안되는 방법으로 경우의수를 다 틀어막았다고 생각했는데, 틀렸다.

 

# 백준 2461 대표 선수
import heapq  # 우선순위 큐 사용을 위한 heapq 모듈

# N: 반의 수 (행), M: 각 반의 학생 수 (열)
N, M = map(int, input().split())

# 각 반의 학생 점수를 정렬하여 저장 (오름차순)
classes = [sorted(list(map(int, input().split()))) for _ in range(N)]

heap = []       # (값, 반 번호, 해당 반에서의 인덱스)를 저장할 최소 힙
max_val = 0     # 현재 선택된 대표 중 가장 큰 값

# 각 반에서 가장 작은 값을 하나씩 선택해서 힙에 넣음
for i in range(N):
    heapq.heappush(heap, (classes[i][0], i, 0))  # (값, 반 인덱스, 학생 인덱스)
    max_val = max(max_val, classes[i][0])       # 현재까지 선택된 값 중 최댓값 갱신

ans = float('inf')  # 최소 (최대 - 최소) 값을 저장할 변수 초기화

# 힙에서 가장 작은 값을 꺼내면서, 하나씩 다음 학생으로 이동
while True:
    min_val, row, idx = heapq.heappop(heap)  # 현재 가장 작은 값, 해당 반, 인덱스
    ans = min(ans, max_val - min_val)        # 현재 조합에서의 max-min 비교 후 최솟값 갱신

    # 만약 해당 반의 학생을 끝까지 확인했으면 종료 (더 이상 조합 불가)
    if idx + 1 == M:
        break

    # 다음 학생 점수로 이동
    next_val = classes[row][idx + 1]
    heapq.heappush(heap, (next_val, row, idx + 1))  # 새 값을 힙에 넣음
    max_val = max(max_val, next_val)  # 새 값이 현재 최댓값보다 크면 갱신

# 정답 출력
print(ans)

계속 못풀기만 하니까 참 열받는다..

 

코드 잘 짜는 사람들이 참 많다.