[アルゴリズム]伯準-2565(電線)/Java
14442 ワード
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Solution {
static int N;
static int max;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());// 전깃줄 갯수
int[] arr = new int[501]; //
int[] dp = new int[501];
//전깃줄이 하나일 경우 0을 출력
if(N == 1) {
System.out.print(0);
return ;
}
max =0 ; // max는 index의 최댓값 ( 전깃줄이 N개지만 인덱스가 N보다 큰 경우를 위해 )
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
arr[start] = end;
max = max > start ? max : start;
}
LIS(arr , dp); //가장 큰 증가하는 수열 구함
//최장 길이 를 구함
int maxDp = 0;
for (int i = 1 ; i <= max ; i++) {
maxDp = maxDp > dp[i] ? maxDp : dp[i];
}
//연결가능한 포트 - 전깃줄이 없는 포트의 갯수 - 최장길이 수열의 길이
System.out.println(max - (max-N) - maxDp);
}
//최장길이 수열 구함
static void LIS(int[] arr , int[] dp) {
int maxIndex;
int maxValue;
for (int i = 1; i <= max; i++) {
if (arr[i] == arr[i - 1]) {
dp[i] = dp[i - 1];
}else if(arr[i] == 0){
continue;
}else {
maxIndex = -1;
maxValue = 1;
for (int j = i - 1; j >= 0; j--) {
//현재 값보다 작고 길이가 긴 인덱스를 찾음
if (arr[j] < arr[i] && maxValue <= dp[j]) {
maxValue = dp[j];
maxIndex = j;
}
}
// 자신보다 작은 값이 없으면 1을 , 있으면 가장 큰 길이를 가지는 값에 +1
dp[i] = maxIndex == -1 ? 1 : dp[maxIndex] + 1;
}
}
}
}
Reference
この問題について([アルゴリズム]伯準-2565(電線)/Java), 我々は、より多くの情報をここで見つけました https://velog.io/@cheal3/알고리즘-백준-2565-전깃줄-자바テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol