https://www.acmicpc.net/problem/31864
문제를 푼 날짜: 2025. 04. 14
#binary_search #data_structures #geometry #hash_set #math #set
내 풀이
/*
Naive Idea: 매 후보지마다 각 과일이 꼬치에 포함되는지 체크
-> O(NM) : 9 * 10^10
-> TLE! :(
Improved Idea:
후보지의 핵심: 기울기 & x부호 (단, y축 위의 점은 기울기 존재x이므로 따로 체크)
-> 과일의 정보를 사전에 저장하면 되지 않을까?
-> Worst Case: Y=X 직선 위에(X>0) 모든 후보지와 과일이 다 존재하는 경우 -> TLE :(
Any Better Idea??
과일의 정보 -> (기울기, x좌표) 로 저장 : ex) key: 기울기[1] -> value: -1, 3, 4 ...
후보지의 정보 -> (기울기, x좌표) 로 저장
-> 만약에 기울기가 같고 x좌표의 부호 역시 같다면 더 큰 것만 남기면 됨!
** Implementation?!
Initial Idea: map 활용, 기울기를 key로 사용
Question: 기울기가 같지만 x좌표의 부호가 다른 경우?
-> 엄... 기울기를 key로 쓰고, value를 vector로 잡은 다음에 x좌표 양수 음수 각각 하나씩 저장하는 꼴?
+) 기울기는 float로 저장해야 할 듯?!
++) 기울기 존재하지 않는 경우 예외 처리하는 게 비효율적 -> 기울기 상한이 10억이니 초과하는 기울기로 임의설정
-> WA 뜬 후 발견! : x=0인 case는 부호 판정하는 부분에서 문제가 생겼닷!! x<->y 스왑으로 해결하자..
+++) 기울기를 key로 사용하는 근본적 문제점(부동소수점문제)?
-> gcd로 나눈 (x, y) 사용
ex. (2, 4) -> (1, 2) / (-3, -6) -> (1, 2)
++++) 기울기 방향 고려하여 부호화
*/
#include <iostream>
#include <map>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <utility>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M; // N: 과일의 수, M: 후보지의 수
cin >> N >> M;
int x, y; // 입력 위한 임시변수
map<pair<int, int>, vector<int>> Fruits;
map<pair<int, int>, int> Candidates;
// 과일 위치 입력받기
for(int i = 0; i < N; i++){
cin >> x >> y;
// y축 위에 있으면 기울기 존재 x, y > 0 이면 (0, 1), y <0 이면 (0, -1) 생성
if(x == 0){
if(y > 0) Fruits[{0, 1}].push_back(y);
else Fruits[{0, -1}].push_back(y);
}
else{
int GCD = gcd(abs(x), abs(y));
Fruits[{x/ GCD, y / GCD}].push_back(x);
}
}
// 후보지 입력받기
for(int i = 0; i < M; i++){
cin >> x >> y;
pair<int, int> slope;
// y축 위에 있으면 기울기 존재 x, y > 0 이면 (0, 1), y < 0이면 (0, -1)
if(x == 0){
if(y > 0){
slope = {0, 1};
x = y;
} else{
slope = {0, -1};
x = y;
}
}
else{
int GCD = gcd(abs(x), abs(y));
slope = {x / GCD, y / GCD};
}
if(Candidates.find(slope) == Candidates.end()) Candidates[slope] = x;
else if(abs(x) > abs(Candidates[slope])) Candidates[slope] = x;
}
// 후보지 key(=기울기) 순회하면서 최댓값 찾기
int max = 0;
for(auto& [key, value] : Candidates){
int cnt = 0;
for(auto& fruit : Fruits[key]){
if(abs(value) >= abs(fruit)) cnt++;
}
if(cnt > max) max = cnt;
}
cout << max;
return 0;
}✅ 아이디어
- 각 후보지마다 전체 과일을 iterate하면서 이 과일이 꼬치에 들어가는 지 체크? -> TLE
- 후보지 & 과일의 정보를 기울기로 저장하자!
-> 각 후보지마다 기울기가 같은 과일들만 조사하면 됨.
(단, y축 위 점의 경우 기울기 존재하지 않으므로 예외 처리 해야 함)
🧠 풀면서 틀렸던 부분 & 얻어가야 하는 내용
-
기울기를 key로 사용할 때, 실수표현은 부동소수점 오차로 인해 의도한 바와 다르게 작동할 수 있음을 간과함!
->pair<int, int>로 기울기 표현함. (기울기벡터 개념,최대공약수로 (x, y)좌표 나눔) -
기울기가 같더라도 방향이 다른 경우 (ex. (2, 4), (-3, -6))의 경우 다르게 취급해야 함!
-> 기울기 벡터 표현 시 부호 고려 -
후보지의 경우 기울기 같고 방향마저 동일하다면 제일 멀리있는 후보지 하나만 고려하면 됨.
-
부호가 같은지 판별하는 조건식 사용할 때 곱하기를 사용했었는데
(v * fruit > 0)
이 경우 int범위를 초과하는 문제가 발생하게 됨!
(자료형의 크기 초과하는 경우 없는지 항상 체크) -
pair<int, int>=><utility>abs( int )=><cstdlib>gcd(int x, int y)=><numeric>
-
기울기를 사용하는 아이디어는 문제에 처음 접근할 때 (Survival Week1 당일) 바로 떠올렸음에도, 이후 구현 및 WA를 고치기 위해 꽤 많은 시간을 투자했음. 문제가 생겼을 때 빠르게 고칠 수 있는 클린 코드가 아닌, 그 순간순간 내 머릿속에 있는 아이디어를 배설하는 식의 주먹구구 코딩을 한 것이 큰 문제인 것 같다... 클린 코드를 쓰는 연습이 많이 필요해 보인다. 아래는 지피티가 개선해준 나의 코드이다.
개선된 코드
#include <iostream>
#include <map>
#include <vector>
#include <numeric> // std::gcd (C++17 이상)
#include <cstdlib> // abs 함수
#include <algorithm>
using namespace std;
using Slope = pair<int, int>;
// 함수: 주어진 점 (x, y)에 대해 정규화된 기울기와 기준 좌표를 구한다.
// - 수직선(x==0)인 경우: y>0이면 key = {0, 1}과 기준 = y, y<0이면 key = {0, -1}과 기준 = y
// - 수직선이 아닌 경우: x, y를 gcd로 나누어 key = {x/g, y/g}와 기준 = x를 사용한다.
void normalizePoint(int x, int y, Slope &slope, int &pos) {
if (x == 0) {
// 수직선인 경우 y>0와 y<0를 분리해서 처리
if (y > 0) {
slope = {0, 1};
pos = y;
} else {
slope = {0, -1};
pos = y;
}
} else {
int g = gcd(abs(x), abs(y));
slope = {x / g, y / g};
pos = x;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int nFruits, nCandidates;
cin >> nFruits >> nCandidates;
// 과일들은 (정규화된 기울기, 기준 좌표) 형태로 저장
// - 수직선인 경우, 기준은 y좌표, 그 외에는 x좌표
map<Slope, vector<int>> fruits;
// 후보지는 같은 기울기 그룹 내에서 양수와 음수 방향 각각 최고 값(원점에서 가장 멀리 떨어진 후보)만 저장
// 따로 후보지 벡터를 관리하는 대신, 한 방향에 대해 단 하나의 후보지만 고려하면 됨
map<Slope, int> candidate;
// 과일 입력
for (int i = 0; i < nFruits; i++) {
int x, y;
cin >> x >> y;
Slope slp;
int pos;
normalizePoint(x, y, slp, pos);
fruits[slp].push_back(pos);
}
// 후보지 입력: 같은 기울기 그룹 내에서는 기준 값의 절대값이 더 큰 후보지만 남긴다.
for (int i = 0; i < nCandidates; i++) {
int x, y;
cin >> x >> y;
Slope slp;
int pos;
normalizePoint(x, y, slp, pos);
// 처음 보는 그룹이면 바로 저장, 이미 있으면 절대값이 더 크면 갱신
if (candidate.find(slp) == candidate.end() || abs(pos) > abs(candidate[slp])) {
candidate[slp] = pos;
}
}
// 각 기울기 그룹 별로 후보지가 포함할 수 있는 과일의 개수를 셈.
// 조건: 후보지(원점에서의 기준 좌표의 절대값)가 과일(해당 그룹에서 저장된 기준 좌표의 절대값)보다 크거나 같아야 한다.
int ans = 0;
for (const auto & [slp, candPos] : candidate) {
// 해당 기울기를 가진 과일이 없다면 넘어감
if (fruits.find(slp) == fruits.end())
continue;
int count = 0;
for (int fruitPos : fruits[slp]) {
if (abs(candPos) >= abs(fruitPos))
count++;
}
ans = max(ans, count);
}
cout << ans << "\n";
return 0;
}
어제보다, 더