음. 이 문제 조금 어렵죠? 스택을 사용하면 O(n)에 해결 가능하다고 하는데

그 풀이를 떠올리기에는 아직 무리입니다.

그렇기 때문에 다른 접근법을 생각해 보셔야 할 거 같습니다.

일단 '사로잡는다'의 의미를 아셔야 하는데요.

자기공보다 크기가 작고, 색깔이 다른 공을 사로잡는다. 에 주목해 주셔야 합니다.

1차 정렬은 크기, 2차 정렬 기준은 색깔로 하면 되겠군요.

case #1에 대해서 제가 말한 기준으로 정렬을 하면 데이터가 이렇게 나옵니다.

1 3

4 8

1 10

3 15

그 다음에가 문제입니다.

각각의 무게에 대해서 color 색으로 칠해져 있는 공들의 무게 합을 업데이트 하기도 그렇고..

발상을 바꿔 봅시다.

각각의 무게가 아니라, 현재 내가 검사한 공까지 color 색으로 칠해져 있는 공들의 무게 합을 업뎃해 봅시다. 일단.

예를 들어서

1 3

2 3

1 5

2 5

4 5

3 7

이 있었다고 해 봅시다. 현재 [2 5]를 가지고 있는 공을 검사했다고 해 봅시다.

그러면 color_sum에는 다음과 같이 저장될 겁니다.

color_sum[] = [0, 8, 8, 0, 5]

그리고 내가 검사한 공들의 total_weight는 21이 되겠군요.

그러면, total_weight에서 뭘 빼야 할까요? 일단 무게가 5인 공들의 무게 합을 빼야겠네요. 그리고 색깔이 같은 공의 무게합을 빼야겠네요.

이건 color_sum에 있는 겁니다.

힌트를 너무 많이 줬네요. 나머지는 집합론에서 배운 내용을 잘 생각하면서 마무리 지어보세요.

감사합니다. 조금 생각해 볼게요.