[C++] BOJ 15975번: 화살표 그리기

ㅎㅎ·2023년 7월 12일
0

BOJ

목록 보기
25/65

BOJ 15975번: 화살표 그리기

서브태스크 문제였다.

문제

입력

출력

표준 출력으로 모든 점에서 시작하는 화살표들의 길이 합을 출력한다.

제한


문제 풀이 - 62점

최종 답을 출력하는 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번이 시간 초과가 뜬다.

문제 풀이 - 성공 100점

정렬을 미리 해두면 경우들을 모두 다 비교할 필요가 없지 않나?!
=> 색상 - 좌표 순서로 오름차순 정렬을 한다.

그럼 가까운 곳에 있는 원소들만 비교하면 됨

#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;
}

야호~~~ 재밌다

profile
Backend

0개의 댓글