백준 15970, 화살표 그리기

문제

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

풀이 방법

점의 최대 갯수는 5000개이고 이를 정렬하고 비교하면 log5000 * 5000 * 2 이므로 완전 탐색으로 풀어도 충분히 시간 내에 돌아간다. 아직 vector의 사용법을 숙지하지 못해서 사용하지 못했는데 이를 숙지하면 메모리 또한 딱 점의 개수 만큼만 사용할 수 있으리라 생각한다.

실수

• sort 내에 일차원 배열의 포인터를 매개변수로 줘야하는데 이차원 배열의 포인터로 넘겨줌
• j + 1 - j 를 j + 1 - j - 1로 작성하는 실수를 저지름
• location과 color의 위치를 혼동함

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>

using namespace std;

int arr[5000][5000] = { 0, }; // 행이 색깔을 나타내고 열의 0번째 index는 항상 그 색깔을 가진 점의 개수를 나타냄

int main() {

	int n; // 점의 개수 및 색깔의 개수

	int color, location;

	int result = 0; 

	int temp1, temp2; // 각각 x-1, x의 차이, x, x+1의 차이를 저장할 변수 

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {


		scanf("%d %d", &location, &color);


		arr[color][0]++;

		int color_num = (arr[color][0]); // arr은 0으로 초기화 되어 있음

		arr[color][color_num] = location;

	}

	for (int i = 1; i <= n; i++) {
		
		sort(arr[i] + 1, (arr[i] + 1) + arr[i][0]); // 정렬
		
	}

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= arr[i][0]; j++) { // 점이 한개만 있는 경우는 존재하지 않음(문제 설명)

			temp1 = (j != 1 ? arr[i][j] - arr[i][j - 1] : 2e9); // 범위에서 벗어났으면 다른 값을 최소 값으로 만듬

			temp2 = (j != arr[i][0] ? arr[i][j + 1] - arr[i][j] : 2e9);

			result += min(temp1, temp2);

		}

	}

	printf("%d", result);

	return 0;

}