[BOJ 2565번] 전깃줄(JAVA)

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

2565번: 전깃줄

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

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
		int num=Integer.parseInt(br.readLine());
		int line[]=new int[501];
		int cnt[]=new int[501];
		int maxIndex=0;
		for(int i=1;i<=num;i++) {
			String s[]=br.readLine().split(" ");
			int temp=Integer.parseInt(s[0]);
			line[temp]=Integer.parseInt(s[1]);
			maxIndex=Math.max(maxIndex, temp);
		}
		for(int i=1;i<=maxIndex;i++) {
			if(line[i]!=0)	cnt[i]=1; 
			for(int j=1;j<=i;j++) {
				if(line[i]>line[j]&&cnt[j]>=cnt[i]) cnt[i]=cnt[j]+1;
			}
		}
		int max=0;
		for(int i=1;i<=maxIndex;i++) {
			max=Math.max(max, cnt[i]);
		}
		int result=num-max;
		bw.write(String.valueOf(result));
		bw.flush();
		bw.close();
	}
}

이 문제는 백준 11053번 문제 "가장 긴 증가하는 부분수열" 문제를 푸셨다면 어렵지 않게 접근하실 수 있는 문제입니다.

아래 링크는 이 블로그의 11053번 문제 풀이 링크입니다.

https://eloquence-developers.tistory.com/42

[BOJ 11053번] 가장 긴 증가하는 부분 수열(JAVA)

int형의 line 배열을 선언하고 A의 a번째 전깃줄이 B의 b번째 전깃줄과 연결되어 있는 상황을 line[a]=b 로 저장했습니다.

line 배열에서 증가하는 가장 긴 부분 수열을 구합니다.

증가하는 부분 수열이 있다는 것은 전깃줄이 겹치지 않는다는 것을 의미하는데요, 그렇기 때문에 결과 값은 전깃줄의 개수에서 증가하는 가장 긴 부분 수열을 빼주면 됩니다.