📚 10800 - 컬러볼

컬러볼

이해

구현 문제이다.

• 크기를 기준으로 오름차순 정렬을 한다.
• 이전 볼은 다음 볼에 영향을 주는 볼이다.

예제

3
1 4
2 4
1 4

• 같은 크기일 때는 제외시켜야 한다.

10  
1 10  
1 10  
2 10  
3 10  
1 9  
1 8  
1 7  
2 3  
3 1  
3 1

• 같은 크기, 같은 색을 선택한 곳은 제외 한다.
• 같은 색일 때는 제외시켜야 한다.

위를 통해 규칙을 알 수 있어, 공식이 나온다.

현재 볼 = (여태까지 총 합) - (같은 수의 크기 합) - (같은 크기의 크기 합) + 내 크기

소스

import sys  
  
read = sys.stdin.readline  
  
n = int(read())  
  
d = {i: [] for i in range(n)}  
answer = [0] * n  
totalSum = 0  
arrC = [0] * 200020  
arrS = [0] * 2020  
  
  
for i in range(n):  
    c, s = map(int, read().split())  
  
    d[i].append(s)  
    d[i].append(c-1)  
  
colorBall = list(d.items())  
  
colorBall.sort(key=lambda x: (x[1]))  
  
for i in range(n):  
    idx, [weight, color] = colorBall[i]  
  
    arrC[color] += weight  
    arrS[weight] += weight  
    totalSum += weight  
  
    answer[idx] = totalSum - arrC[color] - arrS[weight] + weight  
  
    if i != 0 and weight == colorBall[i-1][1][0] and color == colorBall[i-1][1][1]:  
        answer[idx] = answer[colorBall[i-1][0]]  
  
print('\n'.join(map(str, answer)))

참고 : https://sejinik.tistory.com/203