[JAVA] boj 1365 꼬인 전깃줄

문제 링크 : https://www.acmicpc.net/problem/1365

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

4
2 3 4 1

예제 출력 1

1

문제 풀이

다이나믹 프로그래밍과 이분탐색으로 문제를 해결하였다

 

이전에 풀었던 전깃줄 문제와 비슷하게 풀어보았지만 시간초과에 걸렸다 O(n2). 그래서 dp를 사용하되 이분탐색으로 이전에 연결된 전기줄의 개수를 추적하여 전기줄의 개수를 최대화 해주는 과정을 반복하여 해결하였다. O(nlogn)

코드

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

public class Main_BJ_1365_꼬인전깃줄 {
  static int [] dp;
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    
    int N;
    N = Integer.parseInt(br.readLine());
    
    st = new StringTokenizer(br.readLine());
    
    int [] wires = new int [N+1];
    
    for (int i = 1 ; i <= N ; i++) {
      wires[i] = Integer.parseInt(st.nextToken());
    }
    
    dp = new int [N+1];
    int len = 0;
    int idx = 0;
    
    for (int i = 1 ; i <= N ; i++) {
      if (wires[i] > dp[len]) {
        len += 1;
        dp[len] = wires[i];
        continue;
      }
      idx = binarySearch(0, len, wires[i]);
      dp[idx] = wires[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;
  }
}