[BOJ] 백준 1365 : 꼬인 전깃줄 (java)

• 🧪 1365 꼬인 전깃줄

• 📝 문제

• 🧐 핵심 로직

• 💻 최종 코드 (284 ms)

🧪 1365 꼬인 전깃줄

---

난이도 : 🌟 골드 2
유형 : 이분탐색

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

 

📝 문제

---

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

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

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

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

 

입력

 

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

 

출력

 

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

 

🧐 핵심 로직

---

1. 숫자 배열에서 최장 증가 부분 수열의 길이를 구하기 위해 dp 배열을 사용한다.

 

2. dp[0]에는 작은 수를 초기화하여 이후 비교가 편하도록 한다.

 

3.  배열의 각 요소를 순회하면서 현재 요소가 dp 배열의 마지막 값보다 크면 dp에 추가하여 수열의 길이를 늘린다.

    3-1) 만약 작다면 이분 탐색을 통해 dp 배열 내에서 현재 요소가 들어갈 위치를 찾고, 해당 위치의 값을 갱신한다.

 

4. 모든 요소를 순회한 뒤, n에서 최장 증가 부분 수열의 길이를 뺀 값을 출력하여 결과를 구한다.

 

💻 최종 코드 (284 ms)

---

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

public class Main {

    static int n;
    static int[] numbers, dp;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        n = Integer.parseInt(br.readLine());
        dp = new int[n + 1];
        numbers = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = -100000001;
        int len = 0;
        int idx = 0;
        for (int i = 0; i < n; i++) {
            if (numbers[i] > dp[len]) {
                dp[++len] = numbers[i];
            } else {
                idx = binarySearch(0, len, numbers[i]);
                dp[idx] = numbers[i];
            }
        }

        System.out.println(n - len);

        br.close();
    }

    private static int binarySearch(int left, int right, int target) {

        while (left < right) {

            int mid = (left + right) / 2;

            if (dp[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return right;
    }
}