[BOJ] 1365. 꼬인 전깃줄

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

접근 방법

생각을 해보면 꼬이지 않는 가장 긴 사이즈를 전체 사이즈로 빼주면 결과가 나온다.

여기서 꼬이지 않는 가장 긴 사이즈는 증가하는 전봇대의 수열이라고 생각하면 쉽다.

예를 들어서

---

Input

3 , 1, 4, 5, 8 , 2 라고 하면 꼬이지 않으면서 가장 많은 전깃줄을 만들 수 있는 경우는

{ 3, 4 , 5 , 8 } 또는 { 1 , 4, 5 , 8 }이 될 것이다. 즉 수열 중 가장 사이즈가 큰 부분 수열이 된다는 것이다.

또한 내가 놓쳤었던 부분도 알게 되었다. 기존의 나는 LIS를 구할 때

https://dev-room.tistory.com/14?category=792849 의 소스를 들어가보면

ArrayList<Integer> lis = new ArrayList<>();
        lis.add(map[0]);
        for(int i=1; i< N; i++){
            if(map[i] > lis.get(lis.size()-1)){
                lis.add(map[i]);
            }else{
                int bound = Collections.binarySearch(lis,map[i]);
                if(bound < 0){
                    bound = -bound-1;
                }
                lis.remove(bound);
                lis.add(bound,map[i]);
            }
        }
        bw.write(N-lis.size() + "");

위의 코드로 구한 LIS

이런 식으로 직접 새로운 LIS 배열을 만들면서 값을 넣고 있다. 이렇게 되면 시간복잡도가 증가하게 되고 메모리적으로도 낭비가 될 것이다.

아래의 방법으로 LIS를 구현해보도록 하는 것을 연습해보자.

for(int i=1; i< N; i++){
            int s = Arrays.binarySearch(dp,0,cnt,map[i]);
            System.out.println(-s);
            if(dp[cnt-1] < map[i]){
                dp[cnt++] = map[i];
            }else if(dp[0]>map[i]){
                dp[0] = map[i];
            }else{
                int temp = Arrays.binarySearch(dp,0,cnt,map[i]);
                dp[temp < 0 ? -temp-1 : temp] = map[i];
            }
        }

위의 코드로 구현한 LIS

Need Know

1. DP
2. LIS

전체 코드 ( Java )

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int[] map;
    static int[] dp;
    static int cnt = 1;
    public static void main(String[] args) throws IOException {
        set();
        solve();
        bw.flush();
        bw.close();
        br.close();
    }
    static void set() throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new int[N];
        dp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N; i++){
            map[i] = Integer.parseInt(st.nextToken());
        }

    }
    static void solve() throws IOException {
        dp[0] = map[0];
        for(int i=1; i< N; i++){
            if(dp[cnt-1] < map[i]){
                dp[cnt++] = map[i];
            }else if(dp[0]>map[i]){
                dp[0] = map[i];
            }else{
                int temp = Arrays.binarySearch(dp,0,cnt,map[i]);
                dp[temp < 0 ? -temp-1 : temp] = map[i];
            }
        }
        bw.write(N-cnt + "");
    }
}