[백준 15970번] 화살 그리기 (C++)

문제링크 : https://www.acmicpc.net/problem/15970

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int x, y, N, dis;
vector<int>v[5001];
int arr[5001]; //색 갯수 저장

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;

    for(int i=0; i<N; i++)
    {
        cin >> x >> y;
        v[y].push_back(x);
        arr[y]++; //색 갯수 카운팅
    }

    for(int i=1; i<=N; i++) sort(v[i].begin(), v[i].end()); //색깔 별로 정렬

    for(int i=1; i<=N; i++)
    {
        for(int j=0; j<arr[i]; j++)
        {
            if(j==0) dis += (v[i][j+1] - v[i][j]); //맨 처음 부분
            else if(j==arr[i]-1) dis += (v[i][j] - v[i][j-1]); //맨 끝 부분
            else
            {
                dis += min(v[i][j] - v[i][j-1], v[i][j+1]-v[i][j]); //앞뒤 값 중 작은 값 선택
            }
        }
    }

    cout << dis;
    return 0;
}

 

브루트포스 방식의 정렬문제이다.

점과 색깔을 입력할 때, 입력한 색깔의 갯수도 따로 카운팅을 해준다.

 

이후 색깔 별로 따로 정렬을 해주고,

해당 색깔 갯수 만큼 현재 위치를 기준으로 앞 뒤 값 중 더 거리가 짧은 값을 계산하여 담아준다.

이를 모든 위치에 대해 계산해주며, 맨 처음 부분과 맨 끝 부분은 각각 앞 부분과 뒷 부분이 없기에 따로 계산해준다.