[BAEKJOON] 2565 전깃줄

문제 요악

• 알고리즘 분류: 동적 계획법
• 난이도: Gold5
• 문제 요약
  • 전봇대 A, B 사이에 전기줄이 여러개 있다.
  • 교차가 되는 선이 몇개 있는데 최소 몇개의 선을 잘라야 교차 되는 선이 없는기 구해라
• 사이트 주소: https://www.acmicpc.net/problem/2565

2565번: 전깃줄

문제 풀이

 이번 문제는 동적계획법인데 그 중 LIS 최장 증가하는 수열을 구하는 문제이다. LIS 관한 설명은 아래의 사이트에서 확인 하면 된다.

https://jih3508.tistory.com/46

[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

 그럼 저 위에 문제와 LIS 연관성을 대해서 설명을 하겠다. A, B는 전봇대 i는 A전봇대 위치 j는 B전봇대 위치를 가정하자 각 위치를 나타 낸다고 가정 하자. 모든 선인 교차가 안될라면 i >= j 또는 j <= i 가되어야 증명이된다. 즉 i 기준으로 정렬 된수를 B 전봇대를 나열해서 증가하는 수열중 가장 긴것을 구하면 되기때문에 LIS로 풀면 된다. A나 B 중 둘 중 아무거나 정열해도 문제가 없지만 B로 정렬 했으면  A가 가장 긴 수열을 구해야 한다는것만 알고 있으면 된다.

 

Code

 Python

import sys
input = sys.stdin.readline
n = int(input())

wires = [list(map(int, input().split())) for _ in range(n)]
wires.sort()
dp = [1] * n
for i in range(n):
    for j in range(i):
        if wires[i][1] > wires[j][1]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
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[][] wires = new int[n][2];
		int[] dp = new int[n];
		Arrays.setAll(dp, i -> 1);
		StringTokenizer st;
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 2; j++) {
				wires[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 2차원 배열 정렬
		Arrays.sort(wires, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}			
		});
		
		for(int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if(wires[i][1] > wires[j][1]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}
		
		System.out.println(n - Arrays.stream(dp).max().getAsInt());
						
	}
			
}