백준 2565 전깃줄 (JAVA 자바 풀이)

백준 2565 전깃줄 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

 

 

⚔ 입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

 

 

📣 출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

LIS 응용 문제! 

 

결국 문제에서 요구하는 답을 도출하는 논리는 "연결된 수 - 최대로 연결 가능한 전깃줄 수"이다. 

 

최대로 연결 가능한 전깃줄의 수는 곧 연속하는 가장 긴 수열을 의미한다. 

 

그런데 문제는 A가 있고 B가 있는데 무엇을 기준으로 할 것이냐다. 

 

A를 기준으로 정렬하고 정렬된 A에 따라 배열된 B에서 최장 수열을 구하면 그것이 겹치지 않는 전깃줄의 수가 된다. 

 

 

 

 

💡 코드 구현

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bufferedReader.readLine());

		int[] dp = new int[501];
		HashMap<Integer, Integer> lineSet = new HashMap<>(501);
		for (int i = 0; i < N; i++) {
			StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			int numberA = Integer.parseInt(stringTokenizer.nextToken());
			int numberB = Integer.parseInt(stringTokenizer.nextToken());
			lineSet.put(numberA, numberB);
			dp[i] = 1;
		}

		List<Map.Entry<Integer, Integer>> entries = lineSet.entrySet()
				.stream()
				.sorted(Map.Entry.comparingByKey())
				.collect(Collectors.toList());
		ArrayList<Integer> numbers = new ArrayList<>(501);
		for (Map.Entry<Integer, Integer> entry : entries) {
			numbers.add(entry.getValue());
		}

		dp[0] =1;
		int lineMax = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < i; j++) {
				if (numbers.get(i) > numbers.get(j)) {
					dp[i] = Math.max(dp[i], dp[j]+1);
				}
			}
			lineMax = Math.max(lineMax, dp[i]);
		}
		
		System.out.println(N - lineMax);
	}
}