[BOJ] 백준 1365번 꼬인 전깃줄 (Java)

• #1365 꼬인 전깃줄
• 문제 풀이  
  • 설계
• 풀이 코드 

#1365 꼬인 전깃줄

난이도 : 골드 2

유형 : LIS / 이진탐색 

1365번: 꼬인 전깃줄

▸ 문제

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

 

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

 

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

 

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

▸ 입력

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

▸ 출력

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

 

문제 풀이  

LIS 유형의 문제이다. DP만 사용하면 O(n^2)이지만 인덱스 찾는 과정을 이진탐색을 이용해서 구하면 O(n*logn)에 해결할 수 있다. 최소의 전선을 자르기 위해서는 그냥 가장 긴 증가하는 부분 수열을 구한 다음 거기에 해당하지 않는 전선들을 제거해주면 된다.

• 즉, ( 전체 전선의 갯수 - LIS 길이 )를 구해주면 된다.

 

설계

1. 전깃줄에 대한 수열을 입력받는다.
2. 해당 수열에 대한 LIS를 이진탐색을 통해 구한다.
   1. if(arr[i] > dp[len]) i번째 수열의 값이 현재 LIS의 최댓값(dp[len])보다 크다면 최댓값을 갱신한다.
      1. dp[len++] = arr[i];
   2. 만약 i번째 수열의 값이 최댓값과 최솟값의 사이에 있다면 이진탐색을 통해 해당 위치를 구하여 갱신해준다.
      1. idx = binarySearch(0, len, arr[i]);
      2. dp[idx] = arr[i];

 

풀이 코드 

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

public class Main {

	static int[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dp = new int[n+1];
		int len = 0;
		int idx = 0;
		for(int i=0; i<n; i++) {
			if(arr[i] > dp[len]) {
				len += 1;
				dp[len] = arr[i];
				continue;
			} 
			
			idx = binarySearch(0, len, arr[i]);
			dp[idx] = arr[i];
		}
		
		System.out.println(n-len);
				
				
	}
	static int binarySearch(int left, int right, int key) {
		while(left<right) {
			int mid = (left+right)/2;
			if(dp[mid] > key) {
				right = mid;
			}else {
				left = mid+1;
			}
		}
		return right;
	}
}