BOJ 15970번: 화살표 그리기

문제

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 점들의 개수를 나타내는 정수 N이 주어 진다. 다음 N개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x와 y가 주어진다.

출력

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

제한

---

문제 풀이 1 - 31점 오답

정렬 후 완전 탐색을 하면서 좌우 길이 중 작은 수를 저장한다.
1) if 첫번째 원소: answer += v[i+1] - v[i];
2) else if 마지막 원소: { answer += v[i] - v[i - 1]; }
3) else: answer += min(v[i+1] - v[i], v[i] - v[i-1]);

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> b;
vector<int> w;

int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int n, x, y, wc = 0, bc = 0, answer = 0, i;
    bool flag = 0; // 0이 흑, 1이 백

    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> x >> y;
        if (y == 1) { w.push_back(x); wc++; } // 1이 백, 2가 흑
        else { b.push_back(x); bc++; }
    }

    if (wc) { // 백 점이 존재
        sort(w.begin(), w.end());
        for (i = 0; i < wc; i++) {
            if (i == 0) { answer += w[i + 1] - w[i]; }
            else if (i == wc - 1) { answer += w[i] - w[i - 1]; }
            else { answer += min(w[i + 1] - w[i], w[i] - w[i - 1]); }
        }
    }
    
    if (bc) {
        sort(b.begin(), b.end());
        for (i = 0; i < bc; i++) {
            if (i == 0) { answer += b[i + 1] - b[i]; }
            else if (i == bc - 1) { answer += b[i] - b[i - 1]; }
            else { answer += min(b[i + 1] - b[i], b[i] - b[i - 1]); }
        }
    }
    
    cout << answer;

    return 0;
}

틀린 이유:
색의 종류가 흑과 백 2가지라고 잘못 이해했다.

문제 풀이 2 - 100점 성공

2차원 배열 [색상][숫자]
색상 완전 탐색
1) 색상 존재 유무 검사 없으면 continue
2) ** 정렬 후 각 원소의 양쪽 길이 중 짧은 길이 저장

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> v[5000];

int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int n, num, color, i, j, size;
    long long answer = 0;

    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> num >> color;
        v[color].push_back(num);
    }

    for (i = 0; i < 5000; i++) { // 색상 기준 검사
        if (v[i].empty()) { continue; }

        sort(v[i].begin(), v[i].end()); // 정렬

        size = v[i].size() - 1;
        answer += (v[i][1] - v[i][0]) + (v[i][size] - v[i][size-1]);

        for (j = 1; j < size; j++) { answer += min(v[i][j + 1] - v[i][j], v[i][j] - v[i][j - 1]); }
    }
    
    cout << answer;

    return 0;
}