[백준 / Java] 2565번: 전깃줄 (골드5)

문제 풀이 날짜: 2023.05.13
포스트 작성일: 2023.05.23

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2565번: 전깃줄 (골드5) (문제 링크)

 

키워드

동적 계획법(DP), Comparator

 

풀이 접근법

• 전깃줄의 교차 여부는 전깃줄이 연결되어 있는 지점의 번호로 식별할 수 있다.
  • 전깃줄 ⓐ가 4-1 로 연결되어 있는데, 전깃줄 ⓑ는 2-2 로 연결되어 있다면 교차하는 것이다.
  • (전깃줄 ⓑ의 연결 번호 - 전깃줄 ⓐ의 연결 번호) 를 왼쪽 & 오른쪽별로 구했을 때 왼쪽 & 오른쪽 중 한 곳이라도 음수라면(0은 나올 수 없음) 두 전깃줄이 교차된 것이다.
• 문제에서는 설치된 전깃줄 N개의 정보를 준다. 그렇다면 전봇대에 아무 것도 설치되지 않은 상태에서 이 전깃줄 N개 중 몇 개를 교차되지 않게 설치할 수 있을지를 찾아야 한다.
  • DP 배열에 교차되지 않게 몇 개까지 설치할 수 있을지를 담는다.
  • 이렇게 (전체 N개 - 설치 가능한 개수)를 계산하면 그 결과가 철거해야 할 개수가 된다.
• 교차되지 않게 설치하는 방법은 위에 적어두었던 ‘번호의 차’를 이용하면 된다. 번호의 차라고 해봤자 이 번호들이 정렬된 상태(Comparator 구현 필요)에서 A와 B가 동시에 오름차순으로 증가하는지만(LIS) 체크하면 교차 여부를 알 수 있다.
  • 쉽게 말해서, A와 B 배열을 가지고 동시에 LIS를 찾으면 된다.

 

코드

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

public class Q2565 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		
		LinkedList<int[]> poles = new LinkedList<>();
		
		for(int i = 0; i < N; i++) {
			String[] temp = br.readLine().split(" ");
			
			int A = Integer.parseInt(temp[0]);
			int B = Integer.parseInt(temp[1]);
			
			int[] result = {A, B};
			poles.add(result);
		}
		
		Collections.sort(poles, (o1, o2) -> Integer.compare(o1[0], o2[0]));
		
		int max = Integer.MIN_VALUE;
		int[] DP = new int[N];
		Arrays.fill(DP, 1);
		
		for(int i = 1; i < N; i++) {
			int[] now = poles.get(i);
			
			for(int j = 0; j < i; j++) {
				int[] prev = poles.get(j);
				if(prev[0] < now[0] && prev[1] < now[1]) {
					DP[i] = Math.max(DP[j] + 1, DP[i]);
				}
			}
			max = Math.max(DP[i], max);
		}
		
		System.out.print(N - max);
	}

}

---

처음에는 철거해야 할 전깃줄을 찾다가 점화식도 세우지 못하고 갈피를 잡지 못하였다. 전깃줄을 하나씩 제거하면서 (100) 남은 전깃줄(500 * 500) 중에서 교차하는 것을 찾으면(500) 시간초과이기 때문이다. 30분정도 고민하다가, 다른 분들의 풀이를 참고하여 내 방식대로 코드를 작성해보았다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day1/Q2565.java

 

참고한 블로그 링크

https://st-lab.tistory.com/138