서브태스크 문제였다.
표준 출력으로 모든 점에서 시작하는 화살표들의 길이 합을 출력한다.
최종 답을 출력하는 ans를 int형 변수로 정의하면 21점에서 멈춘다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 모든 점을 다 검사하면서 가장 가까운 거리를 저장
vector<pair<int, int>> v; // 좌표, 색상
int main() {
cin.tie(NULL); cout.tie(NULL);
ios_base::sync_with_stdio(false);
int n, i, j, idx, dist, color, mindist;
long long ans = 0;
bool flag; // 같은 색의 서로 다른 점 존재 여부
cin >> n;
for (i = 0; i < n; i++) { // 입력
cin >> idx >> color;
v.push_back({idx, color});
}
for (i = 0; i < n; i++) {
idx = v[i].first;
color = v[i].second;
mindist = 1000000001; // 최소를 구하기 위한 초기값
flag = 0; // 초기화
for (j = 0; j < n; j++) {
if (j != i && color == v[j].second) { // 색이 같은 서로 다른 점 발견
dist = abs(idx - v[j].first); // 화살표 길이 구하기
mindist = min(dist, mindist); // 최솟값 저장
flag = 1;
}
}
if (flag) { ans += (long long)mindist; }
}
cout << ans;
return 0;
}
마지막 4번이 시간 초과가 뜬다.
정렬을 미리 해두면 경우들을 모두 다 비교할 필요가 없지 않나?!
=> 색상 - 좌표 순서로 오름차순 정렬을 한다.그럼 가까운 곳에 있는 원소들만 비교하면 됨
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 1. 색상 2. 좌표 순서로 오름차순 정렬
// 전후의 두 거리를 비교해서 최솟값 저장
vector<pair<int, int>> v; // 좌표, 색상
bool compare(pair<int, int> a, pair<int, int> b) {
if (a.second == b.second) { // 색상이 같다면
return a.first < b.first; // 좌표 오름차순
}
return a.second < b.second; // 같지 않으면 색상 오름차순
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios_base::sync_with_stdio(false);
int n, i, idx, color, front, back, maxnum = 1000000001;
long long ans = 0;
cin >> n;
if (n == 1) { cout << 0; return 0; }
for (i = 0; i < n; i++) { // 입력
cin >> idx >> color;
v.push_back({idx, color});
}
sort(v.begin(), v.end(), compare); // 색상-좌표 오름차순 정렬
for (i = 0; i < n; i++) {
if (i == 0) { // 첫 번째 원소는 뒤만 검사
if (v[i].second == v[i + 1].second) {
ans += (v[i + 1].first - v[i].first);
}
continue;
}
if (i == n - 1) { // 마지막 원소는 앞만 검사
if (v[i].second == v[i - 1].second) {
ans += (v[i].first - v[i - 1].first);
}
break;
}
// 그 사이 원소들은 앞 뒤 검사 후 최솟값 저장
if (v[i].second != v[i - 1].second && v[i].second != v[i + 1].second) {
continue;
}
else {
if (v[i].second == v[i - 1].second) {
front = (v[i].first - v[i - 1].first);
}
else {
front = maxnum;
}
if (v[i].second == v[i + 1].second) {
back = (v[i + 1].first - v[i].first);
}
else {
back = maxnum;
}
ans += min(front, back);
}
}
cout << ans;
return 0;
}
야호~~~ 재밌다