[백준] #10800 컬러볼(python)

수영·2023년 4월 14일

백준

목록 보기

116/117

📌문제

지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다.

공 번호	색	크기
1	1	10
2	3	15
3	1	3
4	4	8

이 경우, 2번 공은 다른 모든 공을 사로잡을 수 있다. 반면, 1번 공은 크기가 더 큰 2번 공과 색이 같은 3번 공은 잡을 수 없으며, 단지 4번 공만 잡을 수 있다.

공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 출력하는 프로그램을 작성하시오.

입력

첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N, 1 ≤ Si ≤ 2,000). 서로 같은 크기 혹은 같은 색의 공들이 있을 수 있다.

출력

N개의 줄을 출력한다. N개의 줄 중 i번째 줄에는 i번째 공을 가진 플레이어가 잡을 수 있는 모든 공들의 크기 합을 출력한다.

예제 입력1

예제 출력1

예제 입력2

예제 출력2

0
0
0

백준 10800번 문제

💡Idea

공🏀의 개수 범위(1 <= N <= 200,000)만 봐도, 공들을 하나하나 확인하며 이중 for문으로 해결하면 $O(N^2)$ 이 되어 시간 초과가 날 것만 같은 문제입니다.

따라서, 공들을 무게 순으로 정렬한 뒤 아래와 같은 계산식을 통해 문제를 해결하였습니다.

i번째 공이 사로잡을 수 있는 공의 크기 합
$=$ 현재까지의 모든 공의 무게 합 $-$ 현재까지의 i번째 공과 색이 같은 공들의 무게 합 $-$ 현재까지의 i번째 공과 무게가 같은 공들의 무게 합

이 때, i - 1번째 공이i번째 공과 색과 무게가 모두 같은 경우 해당 공의 무게에 대한 뺄셈이 두 번 일어납니다.

따라서, 이런 경우에는 따로 처리하여 i - 1번째 공과 같은 값을 가질 수 있도록 해주었습니다.

💻코드

⏰ 시간 : 1116 ms / 메모리 : 100856 KB

import sys
input = sys.stdin.readline

N = int(input())
ans = [0] * N
balls = [tuple(map(int, input().split())) for _ in range(N)]
balls = sorted([(num, ball[0], ball[1]) for num, ball in enumerate(balls)], key=lambda x:[x[2], x[1]])

color_arr = [0] * (N + 1)
size_arr = [0] * 2001
cur_weight = 0

for i in range(N):
    num, color, size = balls[i]
    prev_num, prev_color, prev_size = balls[i - 1]
    if prev_color == color and prev_size == size:
        ans[num] = ans[prev_num]
    else:
        ans[num] = cur_weight - color_arr[color] - size_arr[size]
    color_arr[color] += size
    size_arr[size] += size
    cur_weight += size

print(*ans, sep='\n')

📝코드 설명

변수

balls : 공의 무게 순으로 정렬된 공 정보 리스트로, (공 번호, 공 색깔, 공 무게)로 구성되어 있다.
color_arr : 각 색을 가지고 있는 공들의 무게 합이 저장되는 리스트로, color_arr[i]에는 i번 색을 가지고 있는 공들의 무게 합이 저장된다.
size_arr : 각 무게를 가지고 있는 공들의 무게 합이 저장되는 리스트로, size_arr[i] : 에는 i 무게를 가지는 공들의 무게 합이 저장된다.
cur_weight : 현재까지의 공들의 무게 총 합이 저장된다.

먼저, 공의 색과 무게가 이전 공과 둘 다 동일한지 확인합니다.
1-1. 동일하다면, 이전 공과 같은 값을 가집니다.
1-2. 동일하지 않다면, 현재까지의 무게 합에서 색이 동일한 공들의 무게 합과 무게가 동일한 공들의 무게 합을 빼줍니다.
해당 공의 색과 무게에 맞는 각각의 인덱스에 공의 무게를 더해줍니다.
현재까지의 공의 무게에 공의 무게를 더해줍니다.
정답을 한 줄씩 띄어 출력해줍니다.