백준 10800번 컬러볼 :: 마이구미

이 글은 백준 알고리즘 문제 10800번 "컬러볼" 을 풀이한다.

정올 초등부, 고등부에서 출제된 적이 있다.

본인의 푼 방식은 다른 풀이보다 속도면에서는 떨어진다.

문제 링크 - https://www.acmicpc.net/problem/10800

2019.10.10 수정 완료

 

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

공 번호색크기

1	1	10
2	3	15
3	1	3
4	4	8

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

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

 

---

 

문제의 핵심은 자신보다 크기가 작고 색이 다른 공을 사로잡는 것이다.

공의 개수가 200,000 이기 때문에, 단순한 이중 반복문을 통한 해결은 시간복잡도 O(N^2) 로 시간초과를 낸다.

시간복잡도 NlogN 이하의 시간복잡도가 필요하다.

 

본인은 재채점으로 실패하면서, 다시 풀어보았다.

이전 방식은 부분합을 이용해서 줄였다고 생각했으나, 결국 O(N^2) 방식이였다.

다시 풀면서 크기의 최대값은 2000 이지만, 색상의 최대값은 200,000 인걸 숙지하지 못하기도 했다.

이것을 통해 이차원 배열을 사용하지 않는 접근을 해야한다는 걸 느낄 수도 있다.

 

본인은 문제를 해결하기 위해 새로운 접근이 필요했다.

단순히 크기가 작은 순으로 해결해나가는 것이다.

차례대로 처리하면서, 누적된 값을 이용하면 많은 비용을 줄일 수 있겠다고 생각이 들었다.

 

현재 플레이어의 크기 합 = (누적된 크기값) - (현재 플레이어의 색을 가졌을 때 누적된 크기값)

 

작은 순으로 차례대로 처리하다보니, 각 누적된 값은 결국 본인보다 작은 수들의 누적된 값이 된다.

같은 색의 공이 여러 개 존재할 때, 크기가 큰 것도 존재하겠지만 작은 순으로 처리하다보니, 그 시점에 고려하지 않아도 된다.

본인이 말하고 싶은 것은 작은 순으로 처리하는 것에 많은 의미가 있다는 것이다.

작은 순으로만 처리된다면, 그 시점의 누적된 크기값은 본인보다 작은 수만을 가질 것이고, 같은 색도 본인보다 작은 크기를 가진다.

 

이를 활용한 코드는 다음과 같다.

 

int sum = 0;
for (int i = 0; i < n; i++) {
    Ball ball = input.get(i);

    colors[ball.color] += ball.size;
    sum += ball.size;

    players[ball.id] = sum - colors[ball.color];
}

 

 

 

크기순으로, 크기를 누적시키는 합과 색에 따른 크기를 누적시켜 O(n) 으로 해결할 수 있다.

하지만 같은 크기를 연속적으로 갖는 입력값에 대해 문제가 있었다.

만약 입력값이 다음과 같다고 가정한다.

 

3
1 10
1 10
1 10

 

이러한 입력값은 크기의 합인 sum 이 증가되어도, colors 에 저장된 값을 빼주기 때문에 상관없다.

하지만 색상이 다르면서 크기가 같은 공이 주어지면 문제가 생긴다.

 

3
1 10
2 10
3 10

 

이러한 경우 sum 은 계속 누적되어 증가할테고, colors 는 각 색에 대해 증가한다.

이로 인해, 값은 [0, 0, 0] 이 아닌, [0, 10 - 0, 20 - 0] 이 나오게 된다.

결과적으로 같은 크기에 대한 처리가 필요하게 된다.

 

int sum = 0;
for (int i = 0, j = 0; i < n; i++) {
    Ball a = input.get(i);
    Ball b = input.get(j);

    while (b.size < a.size) {
        sum += b.size;
        colors[b.color] += b.size;

        b = input.get(++j);
    }
    players[a.id] = sum - colors[a.color];
}

 

문제 방향은 동일하고, 같은 크기를 위한 케이스만을 추가해주었다.

현재 공이 다른 공을 잡을 수 있는 경우에만 누적시키는 것이다.

잡을 수 없다면 누적된 값을 사용하고, 있으면 잡을 수 있는 공을 더 누적시킨 후 사용한다.

코드는 복잡하지 않기에, 직접 입력값을 넣고 보면 이해하기 쉬울 것이다.

 

Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2015/10800.java