백준 7568 : 덩치

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

7568번: 덩치

 

N의 크기가 최대 50으로 매우 작으므로 브루트포스로 문제를 해결하면된다.

다만, 나는 N의 크기가 1만 그 이상이라고 생각하고 2차원 누적합을 문제를 해결했다.

 

로직은 다음과 같다.

 

1. weight와 height로 이루어진 2차원 누적합 배열을 만든다.

2. weight가 w, height가 h인 사람보다 순위가 높은 사람은 (w + 1, h + 1)부터 (weight max, height max)까지의 영역의 누적합과 같다. ( (w,h)보다 순위가 높은 사람은 모두 아래 초록색 영역에 포함된다.)

 

 

코드는 아래와 같다.

#include <iostream>

using namespace std;
using pii = pair<int, int>;

pii info[50];
int prefix_sum[201][201];

void solution() {
	int n, weight, height;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> weight >> height;
		info[i].first = weight, info[i].second = height;
		++prefix_sum[weight][height];
	}

	// 가로방향 누적합
	for (int i = 1; i <= 200; i++) {
		for (int j = 1; j <= 200; j++) {
			prefix_sum[i][j] += prefix_sum[i][j - 1];
		}
	}

	// 세로방향 누적합
	for (int i = 1; i <= 200; i++) {
		for (int j = 1; j <= 200; j++) {
			prefix_sum[j][i] += prefix_sum[j - 1][i];
		}
	}

	int max_range = 200;
	for (int i = 0; i < n; i++) {
		weight = info[i].first, height = info[i].second;
		cout << prefix_sum[max_range][max_range] - prefix_sum[max_range][height] 
			- prefix_sum[weight][max_range] + prefix_sum[weight][height] + 1 << '\n';
	}	
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2180 kb

시간: 0 ms