티스토리 뷰
https://www.acmicpc.net/problem/1007
1007번: 벡터 매칭
평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속
www.acmicpc.net
N개의 점을 시점과 종점이 겹치지 않게 벡터를 N/2개를 만들고 벡터들의 합 벡터의 크기를 최소로 만드는 문제입니다.
단순히 20개의 점을 2개씩 묶는다고 생각하면 20C2 * 18C2 * ... 2C2 가 되어 엄청난 경우의 수가 나옵니다
A, B 두 점을 이은 벡터 AB는 결국 원점을 기준으로 OB - OA 입니다. 결국 N개의 점 중 N/2개의 점은 뺄셈을 적용, 나머지는 덧셈을 적용한 것과 합 벡터와 동일합니다. 그렇기 때문에 20개의 점 중 10개를 고르는 문제와 동일해지고 20C10으로 해결할 수 있습니다.
N개의 점 중 N/2개를 골라 원점을 기준으로 벡터 뺄셈을 적용하고 나머지는 덧셈을 적용합니다. 이런 식으로 가장 작은 값을 고르면 됩니다.
(처음에 계속 틀리길래 뭐지 했는데 마지막에 줄바꿈을 안 했었다.... 조심하자!)
코드는 다음과 같습니다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 17142 연구소3 C++ (0) | 2021.06.04 |
|---|---|
| 백준 10840 구간 성분 python3 (0) | 2021.06.02 |
| 백준 18353 병사 배치하기 python3 (0) | 2021.05.28 |
| 백준 1013 Contact C++ (0) | 2021.05.28 |
| 백준 10164 격자상의 경로 (0) | 2021.05.27 |
댓글