지민과 한수의 과일밭 나누기
시간 제한2초메모리 제한128 MB
평면에 놓인 최대 50개의 나무를 점 위를 지나지 않는 직선으로 나누어 두 그룹의 가치 합 차이를 최소화하는 방법을 구하는 문제입니다.
문제
장엄지가 떠난 뒤 김지민과 임한수는 과일밭을 함께 갖게 되었다. 과일밭은 평면이고, 각 과일나무는 한 점으로 나타낸다.
두 사람은 어떤 직선 하나로 과일밭을 나누려고 한다. 직선 위에는 나무가 놓이면 안 된다. 직선의 한쪽에 있는 나무는 김지민이, 다른 한쪽에 있는 나무는 임한수가 갖는다.
각 나무에는 양의 정수 가치가 정해져 있다. 두 사람이 얻는 나무 가치의 합이 최대한 비슷하도록 직선을 골라야 한다.
나무들의 위치와 가치가 주어질 때, 김지민이 얻는 가치의 합과 임한수가 얻는 가치의 합의 차이의 최솟값을 구하시오.
입력
첫째 줄에 나무의 개수 N이 주어진다. N은 2 이상 50 이하의 자연수이다.
둘째 줄부터 N개의 줄에는 각 나무의 x좌표, y좌표, 가치가 차례로 주어진다. 좌표는 0 이상 1,000 이하의 정수이고, 가치는 1 이상 1,000,000 이하의 정수이다. 같은 좌표에 있는 두 나무는 없다.
출력
첫째 줄에 김지민이 가진 나무 가치의 합과 임한수가 가진 나무 가치의 합의 차이로 만들 수 있는 최솟값을 출력한다.