2차원 평면 위에 서로 다른 N개의 점이 주어짐 이 중 직각이등변삼각형을 하나 선택해야 함
조건: 삼각형의 빗변은 x축과 평행 삼각형의 경계 또는 내부에 N개의 모든 점이 포함되어야 함 삼각형의 빗변의 길이가 가장 짧아야 함
💡 핵심 아이디어 (Key Idea)
모든 점이 포함되기 위한 최소 빗변 길이를 구하되,
1. 직각이 빗변의 위쪽에 있는 경우 2. 직각이 빗변의 아래쪽에 있는 경우
이 두 경우를 나눠서 시뮬레이션함:
필요한 정보는 y좌표 별로 x좌표의 최소/최대값만 있으면 됨 (그 사이의 x좌표는 의미없음) 각 y좌표에 대해 해당 선분의 x최소/최대값을 저장하기 위해 unordered_map<y좌표, pair<x좌표최소, x좌표 최대>> 형태를 사용
위 > 아래 / 아래 > 위로 내려가며 삼각형 경계를 확장함.
Silmulation 예제입력 1 : 3개의 좌표 (0 0) (2 3) (4 0) 가 주어지면 map 에 (0, pair(0, 4)) 와 (3, pair(2,2)) 형태로 저장됨
1. 직각이 빗변의 위쪽에 있는 경우 가장 아래 y=0일 때 l = 0, r = 4 > 초기 빗변의 길이 4-0=4 y=1, 2 은 좌표가 없으니 skip 가장 위 y=3 일 때 높이 h=3-0=3
lx=2, rx=2 lx(2)< l+h (0+3) 이면 l = lx-h = 2-3 = -1 >> lx 가 l+h 보다 작다는 의미는 lx를 기존 규칙(l+h)으로 포함할 수 없다는 의미로 l을 더 왼쪽으로 lx-h 로 정한다 >> lx-h 란 lx 기준으로 h만큼 왼쪽으로 이동시킨 값으로 현재 lx를 포함하게 됨.
rx(3) > r-h (4-2) 면 r = rx+h = 3+2 = 5 >> rx 가 r-h 보다 크다는 의미는 마찬가지로 rx 를 기존 규칙(r-h) 로 포함할 수 없다는 의미로 r을 오른쪽으로 >> rx+h 로 이동시키는 데 rx 기준으로 h만큼 오른쪽으로 이동시켜 현재 rx를 포함시키게 됨.
빗변의 거리 r-l = 5-(-1) = 6
2. 직각이 빗면의 아래쪽에 있는 경우 1과 같은 방법으로 가장 위에서 아래로 가면서 l, r 을 조절
두 시뮬레이션 결과 중 작은 값을 출력
✅ C++ Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define BG ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
using ll = long long;
int main(void) {
BG
int n;
cin >> n;
// 각 y별 um[y] pair 로 x의 최소 최대를 pair 로 저장
unordered_map<int, pair<int, int>> um;
for(int i=0; i<n; i++) {
int x, y;
cin >> x >> y;
if(um.find(y) == um.end()) {
um[y] = {x,x};
} else {
um[y].first = min(um[y].first, x);
um[y].second = max(um[y].second, x);
}
}
vector<int> vy;
for(auto e : um) {
vy.push_back(e.first);
}
sort(vy.begin(), vy.end());
// simul 1 위 직각
int by = vy[0];
int l = um[by].first;
int r = um[by].second;
for(int i=1; i<vy.size(); i++) {
int y = vy[i];
int h = y - by;
int lx = um[y].first;
int rx = um[y].second;
if(lx<l+h) l=lx-h;
if(rx>r-h) r=rx+h;
}
int res1 = r-l;
// simul 2 아래 직각
int ty = vy[vy.size()-1];
l = um[ty].first;
r = um[ty].second;
for(int i=vy.size()-2; i>=0; i--) {
int y = vy[i];
int h = ty-y;
int lx = um[y].first;
int rx = um[y].second;
if(lx<l+h) l=lx-h;
if(rx>r-h) r=rx+h;
}
int res2 = r-l;
cout << min(res1, res2);
return 0;
}
Example
> 예제 1
입력 3 0 0 2 3 4 0 출력 6
세 꼭짓점이 (-1.0), (2,3), (5,0)인 직각이등변삼각형이 모든 조건을 만족하며, 빗변의 길이가 6으로 가장 짧다.
> 예제 2
입력 2 0 0 5 2 출력 7
세 꼭짓점이 (0,0), (7,0), (3.5, 3.5)인 삼각형
세 꼭짓점이 (-2,2), (5,2), (1.5, -1.5) 인 삼각형
> 예제 3
입력 4 1 5 3 2 6 6 7 4 출력 10
📝코드 설명 (Code Explanation)
um[y] 각 y좌표별로 x의 최소/최대값 저장 (pair<int,int>) vy 모든 y좌표 정렬용 벡터 res1, res2 위쪽 직각 / 아래쪽 직각 삼각형 각각의 최소 빗변 길이 시뮬레이션 점을 모두 포함하기 위해 삼각형 경계를 높이에 따라 좌우로 확장
경계 확장에 대한 설명은 위 시뮬레이션을 참조해 주세요
✨ 정리하며.. (Wrap-Up & Takeaways)
unordered_map 대신에 map 을 사용하면 y좌표를 자동을 정렬해 줍니다. 다만, 이 경우 map의 첫번째 값을 사용하려면 반복자(iterator) 를 이용해 포인터 멤버접근 연산자인 -> 를 사용하여 auto it = m.begin(); 로 반복자를 만들고 i->first 형태를 사용하여야 합니다. 이에 가독성 측면에서 별도의 vector vy를 사용하였습니다. 정형화된 알고리즘 문제라기 보다는 특정 문제만을 위한 맞춤형 풀이방식인 ad hoc 문제라고 볼 수 있습니다.
그대로 복사하거나 따라서 쳐보고 맞췄다고 하지 마세요 ^^ 자신의 스타일로 변경해 보고 문제를 스스로 풀 수 있어야 자기 것이 됩니다.
That's it for today
Thanks for learning with me. See you in the next post. Have a great day!
