백준_전깃줄(2565) In Java

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

2565번: 전깃줄

문제를 읽었을 때 접근을 못해서 오래걸렸다. 접근방법을 설치가능 최대 개수를 구한다음에 전체 전선개수에서 빼주면 된다.

A전봇대에서 B전봇대 a번째 에 연결됬다면 a번재 이후를 탐색해보면 된다.

 

A전봇대 기준으로 정렬해야 되는데 2차원배열을 정렬을 위해 Comparator를 사용한다.

ar[i][0]: A전봇대, ar[i][1] : B 전봇대

 

Top-Down 코드&풀이

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

public class Main {
    static int[][] ar;
    static  int[] dp;

    static int recur(int N){
        if(dp[N]==0){
            dp[N]=1;
            for (int i = N+1; i <dp.length ; i++) {
                if(ar[N][1]<ar[i][1]){
                    dp[N] = Math.max(dp[N], recur(i) + 1);
                }
            }
        }
        return dp[N];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ar = new int[N][2];
        dp = new int[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st=new StringTokenizer(br.readLine()," ");
            ar[i][0] = Integer.parseInt(st.nextToken());
            ar[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(ar, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });


        int max=0;
        for (int i = 0; i < N; i++) {
            max = Math.max(recur(i),max);
        }
        max = N - max;
        System.out.println(max);

    }
}

 

A전봇대를 기준으로 B전봇대에 연결한 노드값이 더 커야 연결할수 있다. A전봇대를 기준으로 B전봇대에 연결가능 여부를 N+1에서부터 내려오면서 탐색한다.

 

Bottom-Up 코드 &풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] ar = new int[N][2];
        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st=new StringTokenizer(br.readLine()," ");
            ar[i][0] = Integer.parseInt(st.nextToken());
            ar[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(ar, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });

        for (int i= 0; i <N ; i++) {
           dp[i]=1;
            for (int j = 0; j < i; j++) {
                if(ar[i][1]>ar[j][1]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int max=0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, dp[i]);
        }
        max = N - max;
        System.out.println(max);

    }
}

i번째 전봇대에서 연결했으면 다음 탐색은 j번째에 연결된 전봇대보다 값이 커야한다. 그다음 dp[]+1 과 , dp[] 중 큰 값으로 기록한다.

 

출력은 전체 전깃줄 - 설치 가능 최대 전깃줄수 이다.

 

참고 : https://st-lab.tistory.com/138