문제 개요
2차원 좌표 평면 위에 n개의 서로 다른 점 (Xi, Yi)이 주어져 있고, 각 점에는 가중치 Wi가 부여되어 있습니다. 이때 기울기가 45도인 직선을 하나 그어서, 직선 양쪽에 위치한 점들의 가중치 합이 서로 같아지도록 만들 수 있는지 확인해야 합니다.
예를 들어 입력이 [[-1,1,3], [-2,1,1], [1,-1,4]]라면 출력은 True입니다.
핵심 아이디어
기울기가 45도인 모든 직선은 x − y = c 꼴의 방정식으로 표현할 수 있습니다. 상수 c의 값을 조정하면 직선을 대각선 방향으로 평행 이동시킬 수 있습니다. 각 점 (Xi, Yi)에 대해 d = Xi − Yi를 계산하면 점의 위치를 다음과 같이 판별할 수 있습니다.
- d < c인 점 → 직선의 한쪽 면에 위치
- d > c인 점 → 직선의 반대쪽 면에 위치
- d = c인 점 → 직선 위에 정확히 놓임
즉, 복잡한 기하학적 문제가 "d값 수직선 위의 적절한 위치를 찾아 왼쪽 가중치 합과 오른쪽 가중치 합을 같게 만들 수 있는가"라는 1차원 누적합(prefix sum) 문제로 단순화됩니다.
알고리즘 단계
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- n := 벡터 v의 크기
- 맵 weight_at_x 정의 (d값별 가중치 합을 저장)
- max_x := -2000, min_x := 2000으로 초기화
- i := 0부터 n 미만까지 반복:
• temp_x := v[0][i] − v[1][i]
• max_x := max(max_x, temp_x), min_x := min(min_x, temp_x)
• weight_at_x[temp_x] += v[2][i] - 배열 sum_temp를 정의하고 0을 삽입
- x := min_x부터 max_x까지 반복하며 sum_temp의 끝에 (마지막 원소 + weight_at_x[x])를 추가하여 누적합 배열을 완성
- total_sum := sum_temp의 마지막 원소 (전체 가중치 합)
- partition_possible := false로 초기화
- i := 1부터 sum_temp의 크기 미만까지 반복:
• sum_temp[i] == total_sum − sum_temp[i]이면 → 인접한 두 d값 사이에 직선을 그을 수 있으므로 partition_possible := true
• sum_temp[i−1] == total_sum − sum_temp[i]이면 → 직선이 특정 점을 정확히 통과하는 경우이므로 partition_possible := true - partition_possible 반환
두 번째 조건이 중요한 이유는, 어떤 점의 d값이 정확히 c와 일치할 때 그 점은 어느 쪽 면에도 속하지 않기 때문에 분할이 성립할 수 있기 때문입니다.
구현 예제
다음 C++ 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void is_valid_part(vector<vector<int>> &v){
int n = v.size();
map<int, int> weight_at_x;
int max_x = -2000, min_x = 2000;
for (int i = 0; i < n; i++) {
int temp_x = v[0][i] - v[1][i];
max_x = max(max_x, temp_x);
min_x = min(min_x, temp_x);
weight_at_x[temp_x] += v[2][i];
}
vector<int> sum_temp;
sum_temp.push_back(0);
for (int x = min_x; x <= max_x; x++) {
sum_temp.push_back(sum_temp.back() + weight_at_x[x]);
}
int total_sum = sum_temp.back();
int partition_possible = false;
for (int i = 1; i < sum_temp.size(); i++) {
if (sum_temp[i] == total_sum - sum_temp[i])
partition_possible = true;
if (sum_temp[i - 1] == total_sum - sum_temp[i])
partition_possible = true;
}
printf(partition_possible ? "TRUE" : "FALSE");
}
int main() {
vector<vector<int>> v = {{-1,1,3},{-2,1,1},{1,-1,4}};
is_valid_part(v);
}입력
{{-1,1,3},{-2,1,1},{1,-1,4}}출력
TRUE
복잡도 분석
시간 복잡도는 점의 개수 n과 d값의 범위 R에 대해 O(n + R)이며, 공간 복잡도는 O(R)입니다. 좌표 범위가 제한적인 경우 매우 효율적으로 동작합니다.