[백준 15970] 화살표그리기

난이도

실버 IV

📜문제

https://www.acmicpc.net/problem/15970

🔎접근

• 모든 점에 대해서 같은 색깔을 가진 다른 점이 항상 존재한다.
  • 모든 점에서 화살표를 항상 그릴 수 있다.

• 화살표의 개수는 좌표의 수만큼 나온다.

• 백터에 색깔을 정렬을 해서 같은 색깔끼리 비교를 한다.
  • 큐나 스택은 좌표가 남아있어야하는데 pop시켜버리면 값을 알수가 없다.

벡터의 정렬을 통한 모든 점에서의 화살표길이 비교

🌞풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

vector<pair<int, int>> v;
vector<int> compare_v;

int result; // 총 합

bool compare(pair<int, int> a, pair<int, int> b)
{
	return a.second < b.second;
}

int shortpath()
{
	sort(compare_v.begin(), compare_v.end());
	for (int i = 1; i < compare_v.size()-1; i++) // 맨앞 맨뒤 제외
	{
		int before = compare_v[i] - compare_v[i - 1]; // 앞의 길이
		int after = compare_v[i + 1] - compare_v[i]; // 뒤의 길이

		if (before < after) result += before;
		else result += after;
	}
	result += compare_v[1] - compare_v[0]; // 맨 앞
	result += compare_v[compare_v.size() - 1] - compare_v[compare_v.size() - 2]; // 맨 뒤

	return result;
}

int main()
{
	int num = 0;
	cin >> num;

	int value, type = 0;
	for (int i = 0; i < num; i++)
	{
		cin >> value >> type;
		v.push_back(make_pair(value, type));
	}

	sort(v.begin(), v.end(), compare); // 색깔에 따른 오름차순 정렬


	int type_start = v[0].second;
	for (int i = 0; i < num; i++)
	{
		if (type_start == v[i].second) compare_v.push_back(v[i].first); // 색깔이 같으면 백터에 넣는다.
		else
		{
			shortpath();// 색깔이 달라지면 비교
			compare_v.clear(); // 비교 백터 비우고
			type_start = v[i].second; // 비교 타입 저장
			compare_v.push_back(v[i].first); // 비교 벡터에 다시 입력
		}
	}
	shortpath();
	cout << result << "\n";

	return 0;
}

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기