[C++] BOJ(백준) 10800 컬러볼

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

10800번: 컬러볼

 

누적 합과 구현 문제다.

 

자신보다 사이즈가 큰 공을 찾기 위해서는 정렬이 필요하다고 생각했다.

이중 반복문으로 하나하나 검사를 하면 시간초과가 날 것 이기 때문에 효율적인 방법을 찾으려 했다.

 

처음에는 반복문 하나에 누적합을 구하는 방법을 사용했다.

for (int i = 1; i <= n; i++) {
	sum[i] = sum[i - 1] + arr[i].size;
	colorSum[arr[i].color] += arr[i].size;
	re[arr[i].index] = sum - color[arr[i].color];
}

이 경우 사이즈가 같은 공에 대해서도 계산되는 문제가 있었다.

 

이를 해결하기 위해 공의 사이즈가 같은 경우에 대해 따로 처리했다.

그러나 몇 퍼가지 못해 틀렸습니다가 떴다.

 

이 글을 쓰면서 코드를 한 번 더 보다가 틀린 이유를 찾았다.

색이 같은 공에 대해 사이즈를 계산할 때, color[i] = color[i - 1]; 이 부분이 문제였다.

현재 공 색깔과 이전 공 색깔이 같지 않으므로 당연히 틀릴 수 밖에 없었다.

for (int i = 1; i <= n; i++) {
	sum[i] = sum[i - 1] + arr[i].size;ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ/////
	if (arr[i].size == arr[i - 1].size) realsum[i] = realsum[i - 1];
	else realsum[i] = sum[i];

	colorSum[arr[i].color] += arr[i].size;
	if (arr[i].size == arr[i - 1].size) color[i] = color[i - 1];
	else color[i] = colorSum[arr[i].color];
    
	re[arr[i].index] = sum[arr[i].index] - color[arr[i].color];
}

 

그래서 찾은 방법은 이중 반복문이나 누적 합을 이용하여 전체 배열을한 번만 탐색하는 것이다.

바깥 반복문은 처음부터 끝까지 탐색을 하고,

내부 반복문은 i-1번째에서 끝난 지점부터 i보다 작고 공의 사이즈가 더 작을 때까지만 반복한다.

이렇게 하면 사이즈가 중복되더라도 제대로 된 계산을 할 수 있다.

 

#include <iostream>
#include <algorithm>
using namespace std;

struct ball {
    int size, color, index;
};

ball arr[200001];
int color[200001];
int re[200001];

// 정렬에 이용되는 함수 (정렬 기준)
bool cmp(ball& b1, ball& b2) {
    return b1.size < b2.size;
}

int main() {
    // 입출력 속도를 단축시키기 위함
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;  cin >> n;
    for (int i = 1; i <= n; i++) {
        int c, s;   cin >> c >> s;
        arr[i] = { s, c, i };
    }

    sort(arr + 1, arr + n + 1, cmp);

    int sum = 0, j = 1;
    // 전체 탐색
    for (int i = 1; i <= n; i++) {
        // i번째 전 까지만 탐색하되, 공의 사이즈가 같으면 멈춤
        for (j; j < i && arr[i].size > arr[j].size; j++) {
            // 사이즈의 누적 합과 색깔 별 사이즈 누적 합을 구함
            sum += arr[j].size;
            color[arr[j].color] += arr[j].size;
        }
        re[arr[i].index] = sum - color[arr[i].color];
    }

    for (int i = 1; i <= n; i++)
        cout << re[i] << "\n";
}

༼ つ ◕_◕ ༽つ