[python] BOJ 10800 컬러볼

문제 설명

플레이어는 각각 특정한 색과 크기를 가진 공 하나를 조종하여 게임에 참여하는데 다른 공을 잡아도 본인의 공의 색과 크기는 변하지 않는다. 플레이어가 가지고 있는 공보다 크기가 작고 색깔이 다른 공만 잡을 수 있다. 각 플레이어 별로 주어진 공으로 잡을 수 있는 모든 공들의 크기의 합을 출력하는 것이 문제의 목표이다. 풀이 과정을 대략적인 그림으로 보면 아래와 같다.

코드 설명

import sys

n = int(input())
INF = 200000
balls = []

for i in range(n):
    color, size = map(int, sys.stdin.readline().split())
    balls.append((size, color, i))
    #공의 size, color, input 순서(player)에 대한 정보를 넣는다

balls.sort()
color_count = [0] * (INF + 1)
total = 0
j = 0
ans = [0] * (n + 1)
for i in range(n):
    while balls[j][0] < balls[i][0]:  # 문제의 제한조건에서 player가 잡을 수 있는 전제 조건 중 하나인
    				      # 나의 공보다 사이즈가 작아야 잡을 수 있다의 조건을 충족시켜주기 위한 부분
        color_count[balls[j][1]] += balls[j][0]
        total += balls[j][0]
        j += 1
    ans[balls[i][2]] = total - color_count[balls[i][1]] # 누적합 계산
    							# 나의 공보다 작은 공들의 크기 총합에서 나와 색깔이 같은
                                			# 공들의 합을 빼준다
                                            		# 문제의 제한 조건 중 하나인 색깔이 다른 공만 잡을 수 있다
                                                    	# 여기까지 완료해 주면 문제의 두가지 제한조건이 완성

for i in range(n):
    print(ans[i])
    

주의 할 점

"같은 색은 잡을 수 없다 or 작은 것만 잡을 수 있다" 라고 바꿔보면 문제 난이도가 수직 하강하는데 두가지를 동시에 만족 해야 하는 문제로 간단한 덧셈 뺄셈 같아 보이지만 겹치지 않게 원하는 값을 뽑을 수 있게 조건을 걸어주는 것이 중요하다. 또한 문제에서 들어 올 수 있는 공의 갯수의 범위(1 ≤ N ≤ 200,000)가 매우 크기 때문에 이 부분을 줄일 수 있는 방법을 생각해야 한다.

문제 풀러 가기

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