| TimeLimit | MemoryLimit | Condition | TAG |
|---|---|---|---|
| 2s | 128MB | (3<= N <= 10,000 3 <= K <= 1,000) | BruteForce, Two Pointer(?) |
N개의 점들이 원의 내부에 찍혀 있다. 이 원을 K개의 부채꼴로 등분하려 한다. 즉, 각 부채꼴의 중심각이 360/K도가 되어야 한다. 부채꼴을 어떻게 나누느냐에 따라서 각 부채꼴에 찍혀 있는 점의 개수가 달라질 수 있다.
N개의 점들이 찍혀 있는 각도가 주어졌을 때, 가장 많은 점이 찍혀 있는 부채꼴에 찍혀 있는 점의 개수와, 가장 적은 점이 찍혀 있는 부채꼴에 찍혀 있는 점의 개수의 차이의 최솟값을 구하는 프로그램을 작성하시오.
단, 부채꼴의 테두리에 점이 포함되어서는 안 된다.
디게 오랜만에 문제가 굉장히 재미있었다. 머리가 말랑말랑 해지는 기분이랄까.. 확실히 유사코 문제가 재밌는게 많은 듯 하다.
처음에 어? 이거 그냥 브포 돌리면 되겠는데 했는데 다행이 되어서 다행이다 나중에 다른 코드들 보니까 브포 보다는 그냥 이분탐색만 있어서 약간 당황
그리고 그 벡터쓰는 버릇을 없애야겠다. 이게 나중가니까 너무 벡터 함수에 의존하는 경향이 생기는 것 같아서 최대한 함수 없이 구현하려고 노력하고 있다. 다음부터는 배열을 주로 사용하기로!
처음에 틀렸던 것은 360/K로 해서 등분하는게 아니라 K개의 선을 그어서 나오는거 찾는 줄 알았따. 정말 놀랍게도 그렇게 두번을 제출했고 레전드를 찍었다.
그 이후에 다시 읽고서 아 등분이구나! 하고 다시 풀어서 시초(time out)맞고 다시 풀어서 AC 맞았따.. 문제 풀면서 디게 재밌게 풀었고 좀 기억에 남을 듯 하다.
코드는 약간 설명하자면, 나중에 점 계산 빠르게 돌리기 위해서 정렬 돌린다. 어차피 점을 나누는게 제일 중요하기 때문에 다른 곳은 볼 필요가 없다고 생각했다. 이 문제의 경우 최적의 부채꼴 분할은 반드시 어떤 점을 정확히 부채꼴의 경계에 두는 경우를 포함하기 때문에 그 점을 시작으로 잡고 돌렸다.
그러고 정렬된거 토대로 개수를 세주고 이후에 result에 반영
그 360 더하는 거는 진짜 와… 이걸 어찌저찌 해봐서 됐는데
만약에 300도에서 시작하는 점이 있으면, 여기는 k가 3일 때 120도 만큼 잘라야되니.. 넘어가죠 이걸 고려해서 연산을 쉽게하려고 하는 겁니다ㅏ
정답 코드
요런 문제의 경우 파이썬이 아니니까 data type의 범위 잘 신경쓰시고 오차도 신경을 좀 써주셔야 될 것 같아용!! 이 문제는 그런게 덜하지만 다른 문제는 좀 이상하게 나오는 경우가 있다고 들었거든요!
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int N, K;
cin >> N >> K;
vector<double> angles(N);
for (int i = 0; i < N; i++) cin >> angles[i];
sort(angles.begin(), angles.end());
vector<double> extended_angles = angles;
for (double angle : angles) {
extended_angles.push_back(angle + 360);
}
ll realResult = 1e12;
double sector_size = 360.0 / K;
for (int i = 0; i < N; i++) {
vector<ll> result(K, 0);
double start = angles[i];
int left = 0;
for (int j = 0; j < K; j++) {
double sectorStart = start + j * sector_size;
double sectorEnd = sectorStart + sector_size;
while (left < extended_angles.size() && extended_angles[left] < sectorEnd) {
if (extended_angles[left] >= sectorStart) {
result[j]++;
}
left++;
}
}
if (!result.empty()) {
ll maxResult = 0;
ll minResult = 1e12;
for (ll value : result) {
maxResult = max(maxResult, value);
minResult = min(minResult, value);
}
realResult = min(realResult, maxResult - minResult);
}
}
cout << realResult;
return 0;
}
// 345 94 218이거 자기 전에 풀어서 그런가.. 스네이크랑 카멜이랑 섞여 있네요 와 ㄹㅈㄷ 이게 요즘 코드에서도 발견되네