백준 15970 - 화살표 그리기

[문제 바로가기]

1. 유형

정렬, 브루트포스

 

2. 풀이

점의 범위가 100000이기 때문에 O(N^2)이면 시간초과입니다.

따라서 동적프로그래밍을 썼습니다.

 

설계

1) 위치 순서대로 입력값 정렬

2) 색깔별로 큐 배열 만들고, 같은 색 끼리 큐에 삽입(굳이 큐를 사용안하고 배열 사용해도 됨)

3) 같은 색 끼리의 위치를 빼서 DP에 최소값 저장

 

예제1을 기준으로 설명하면, 색깔1의 위치는 0, 3, 5 순서로 입력됩니다.

0과 3의 차이는 3이고, DP[0]=3, DP[3]=3 을 입력.

3과 5의 차이는 2이고, DP[3]=2 (기존 값이 3이었는데, 2가 더 작으므로 초기화), DP[5]=2

 

위 과정을 색깔별로 해주면 됩니다.

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = stoi(st.nextToken());
		int M = 100001;
		Queue<Integer> q[] = new LinkedList[N + 1];
		for (int i = 0; i <= N; i++) {
			q[i] = new LinkedList<>();
		}
		int dp[] = new int[M];
		for(int i=0; i<M; i++) {
			dp[i] = 987654321;
		}
		Queue<int[]> pq = new PriorityQueue<>((int[] a,int[] b)->{
			return a[0]-b[0];
		});
		int maxindex=0;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int pos = stoi(st.nextToken());
			int color = stoi(st.nextToken());
			pq.add(new int[] {pos, color});
			maxindex = Math.max(maxindex, pos);
		}
		while (N-- > 0) {
			int arr[] = pq.poll();
			int pos = arr[0];
			int color=arr[1];
			if (!q[color].isEmpty()) {
				int pos2 = q[color].poll();
				int minval = Math.abs(pos-pos2);
				if(dp[pos] > minval) {
					dp[pos] =minval;
				}
				if(dp[pos2] > minval) {
					dp[pos2] = minval;
				}
			}
			q[color].add(pos);
		}
		int sum=0;
		for(int i=0; i<=maxindex; i++) {
			if(987654321 == dp[i]) continue;
			sum+=dp[i];
		}
		System.out.println(sum);
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}