[백준] 2565번 전깃줄 _ JAVA ( 주석 설명 )

1-(1)번

- 본인(N)을 중심으로 0~N-1을 탐색하며 작은 값을 찾아, 가장 긴 증가하는 부분 수열을 찾는다.

→ Top-down 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[][] ary; //입력받은 수열을 담을 공간이다.
    static int[] dp; //증가하는 부분수열을 담을 공간이다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        ary = new int[N][2];
        dp = new int[N];

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            ary[i][0] = Integer.parseInt(st.nextToken()); //전깃줄 A 전봇대 위치
            ary[i][1] = Integer.parseInt(st.nextToken()); //전깃줄 B 전봇대 위치
        }

        //A 전봇대 위치를 중심으로 정렬 진행
        //Why?
        //그래야 A 전봇대 위치로 B 전봇대의 값을 비교하며, 설치할 수 있는 전깃줄의 갯수를 파악할 수 있다.
        Arrays.sort(ary, (int[] o1, int [] o2) ->{
            return o1[0] - o2[0];
        });

        //설치 가능한 전깃줄의 갯수를 파악하자.
        int LIS = 0;
        for(int i=0;i<N;++i) {
            LIS = Math.max(LIS,solve(i));
        }

        //교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.
        System.out.println(N-LIS);
    }

    //Top-down 방식
    //설치해야 할 전깃줄 개수 찾기(LIS)
    private static int solve(int N) {
        if(dp[N]==0){
            //기본적으로 자기 자신이 있으므로, 디폴트 값은 1개이다.
            dp[N] = 1;

            //본인(N)을 중심으로 작은 값들을 탐색하며, 가장 긴 증가하는 부분 수열을 찾는다.
            for(int i=0;i<N;++i){
                if(ary[i][1]<ary[N][1]){
                    dp[N] = Math.max(dp[N], solve(i)+1);
                }
            }
        }

        return dp[N];
    }
}

 

---

 

1-(2)번

- 본인(N)을 중심으로 N+1~ary.length를 탐색하며 큰 값을 찾아, 가장 긴 증가하는 부분 수열을 찾는다.

→ Top-down 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[][] ary; //입력받은 수열을 담을 공간이다.
    static int[] dp; //증가하는 부분수열을 담을 공간이다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        ary = new int[N][2];
        dp = new int[N];

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            ary[i][0] = Integer.parseInt(st.nextToken()); //전깃줄 A 전봇대 위치
            ary[i][1] = Integer.parseInt(st.nextToken()); //전깃줄 B 전봇대 위치
        }

        //A 전봇대 위치를 중심으로 정렬 진행
        //Why?
        //그래야 A 전봇대 위치로 B 전봇대의 값을 비교하며, 설치할 수 있는 전깃줄의 갯수를 파악할 수 있다.
        Arrays.sort(ary, (int[] o1, int [] o2) ->{
            return o1[0] - o2[0];
        });

        //설치 가능한 전깃줄의 갯수를 파악하자.
        int LIS = 0;
        for(int i=0;i<N;++i) {
            LIS = Math.max(LIS,solve(i));
        }

        //교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.
        System.out.println(N-LIS);
    }

    //Top-down 방식
    //설치해야 할 전깃줄 개수 찾기(LIS)
    private static int solve(int N) {
        if(dp[N]==0){
            //기본적으로 자기 자신이 있으므로, 디폴트 값은 1개이다.
            dp[N] = 1;

            //본인(N)을 중심으로 N+1~ary.length를 탐색하며, 가장 긴 증가하는 부분 수열을 찾는다.
            for(int i=N+1;i< ary.length;++i){
                if(ary[i][1]>ary[N][1]){
                    dp[N] = Math.max(dp[N], solve(i)+1);
                }
            }
        }

        return dp[N];
    }
}

 

---

 

2번

→ Bottom-up 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[][] ary; //입력받은 수열을 담을 공간이다.
    static int[] dp; //증가하는 부분수열을 담을 공간이다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        ary = new int[N][2];
        dp = new int[N];

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            ary[i][0] = Integer.parseInt(st.nextToken()); //전깃줄 A 전봇대 위치
            ary[i][1] = Integer.parseInt(st.nextToken()); //전깃줄 B 전봇대 위치
        }

        //A 전봇대 위치를 중심으로 정렬 진행
        //Why?
        //그래야 A 전봇대 위치로 B 전봇대의 값을 비교하며, 설치할 수 있는 전깃줄의 갯수를 파악할 수 있다.
        Arrays.sort(ary, (int[] o1, int [] o2) ->{
            return o1[0] - o2[0];
        });

        solve();

        //설치 가능한 전깃줄의 갯수를 파악하자.
        int LIS = 0;
        for(int i=0;i<N;++i) {
            LIS = Math.max(LIS,dp[i]);
        }

        //교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.
        System.out.println(N-LIS);
    }

    //Bottom-up 방식
    //설치해야 할 전깃줄 개수 찾기(LIS)
    private static void solve() {
        //i의 반복문은 거꾸로 탐색해주어야, dp[i]=1로 초기화해주고 dp[i]를 계산할 수 있다.
        for(int i= ary.length-1;i>=0;--i){
            dp[i] = 1;
            //j는 크게 상관 x
            for(int j= i+1;j< ary.length;++j){
                if(ary[i][1] < ary[j][1]){
                    //dp[j]+1이 더 크면 갱신해준다.
                    dp[i] = Math.max(dp[i] , dp[j]+1);
                }
            }
        }
    }
}