백준 15970 - 화살표 그리기

백준 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 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 pq = new PriorityQueue<>((int[] a,int[] b)->{ return a[0]-b[0]; }); int maxindex=0; for(int i=0; i 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); } }

from http://moons-memo.tistory.com/264 by ccl(A) rewrite - 2021-11-07 14:01:54