[python] 백준 2923 숫자 게임

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

2923번: 숫자 게임

 

 

문제 해결

• n번 숫자 쌍이 추가 될 때마다 A와 B의 원소를 쌍을 맞춰 각 쌍의 최댓값의 최솟값을 구하는 문제
• 쉽게 직관적으로 A의 오름차순 수열 $a_{1}$, $a_{2}$ , ... 라 하고  B의 내림 차순 수열 $b_{1}$, $b_{2}$, ..라 할 때 answer = min($a_{i}+b_{i}$) 가 될 것이다.
• 그러므로 각 숫자의 개수를 인지한 다음 하나씩 짝을 맞추었을 때 합의 최댓값을 구하면 된다.
• 그리고 숫자가 추가되기전 원래대로 수열을 리셋시키고 추가로 숫자를 받아야한다.(사실 중간에 삽입해도 되기는 한데... 복잡도가 오히려 커질수 있다...)

 

CODE

# 2923
import sys
input = sys.stdin.readline
import copy

def minmaxsum():
    originalA = copy.deepcopy(A)
    originalB = copy.deepcopy(B)
    a, b = findindex(A, 1, False), findindex(B, 100, True) # 존재하는 숫자 찾기
    minVar = min(A[a], B[b])
    A[a] -= minVar
    B[b] -= minVar
    result = 0
    while a != -1 and b != -1:
        result = max(result, a + b)
        a, b = findindex(A, a, False), findindex(B, b, True)
        minVar = min(A[a], B[b])
        A[a] -= minVar
        B[b] -= minVar
    for i in range(1, 101): # 다시 리셋
        A[i] = originalA[i]
        B[i] = originalB[i]
    return result


def findindex(nums, startindex, isreversed):
    if isreversed == False:
        for i in range(startindex, 101):
            if nums[i] >= 1:
                return i
    else:
        for i in range(startindex, 0, -1):
            if nums[i] >= 1:
                return i
    return -1


if __name__ == "__main__":
    n = int(input())
    A = [0] * 101
    B = [0] * 101
    for _ in range(n):
        a, b = map(int, input().split())
        A[a] += 1
        B[b] += 1
        answer = minmaxsum()
        print(answer)