[Java] 백준 2565 - 전깃줄

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

2565번: 전깃줄

 

이미 개수를 구한 부분들을 탐색하면서

1. 현재 노드에 연결된 전깃줄 인덱스 > 이전 노드에 연결된 전깃줄 인덱스

2. 1의 조건을 만족하는 값들중에 연결된 전깃줄의 수가 최대인 경우

이 두 조건을 만족하는 값을 구하고 +1을 해주었다.!

 

 

나름 효율성 높인다고 HashMap 사용해서 dp 값 설정해주었다 ㅋㅋ

 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int ans = 0;
		
		ArrayList<Integer> arr = new ArrayList<>();
		HashMap<Integer, Integer> hm = new HashMap<>();
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			arr.add(a); hm.put(a, b);
		}
		
		Collections.sort(arr);
		
		HashMap<Integer, Integer> dp = new HashMap<>();
		
		for(int i=0; i<N; i++) {
			int now = arr.get(i);
			int prevN = 0;
			for(int j=i-1; j>=0; j--) {
				int prev = arr.get(j);
				if(hm.get(prev) < hm.get(now))
					prevN = Math.max(dp.get(prev), prevN);
			}
			dp.put(now, prevN+1);
			ans = Math.max(ans, prevN+1);
		}
		
		System.out.println(N-ans);
	}
}