[알고리즘] 백준 2565 전깃줄 -dp-

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

2565번: 전깃줄

 

 

 

이어 단계별 dp 문제를 풀어봤습니다. LIS 라는 것을 안보고 그냥 풀었었는데 LIS 개념은 다음 사이트나 구글링을 통해 볼 수 있습니다. Longest Increasing Subsequence, 최장증가부분수열 입니다.

https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

최적화된 LIS(Longest Increasing Subsequence) 알고리즘과 해 찾기

 

 

전깃줄 합선이 안되게 최소로 제거해야할 전깃줄을 구하는 문제였습니다. 역발상으로 전깃줄 제거가 아닌 최대 설치개수를 dp, LIS 로 구하고 최대 개수에서 뺴면 간단해지는 문제였습니다.

A전깃줄로 먼저 오름차순 정렬을 하여(그럼 반복문 돌며 B만 값 비교하여 신경쓰면 됨) 최대로 합선안되게 설치할 수 있는 전깃줄의 개수를 구하고 전체 개수에서 뺌으로써 최소제거 개수 결과를 도출할 수 있었습니다.

설명은 주석에 적어놨습니다.

 

풀이는 다음과 같습니다.

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] num = new int[n + 1][2]; //[][1] : A 전깃줄 번호, [][2] : B 전깃줄 번호
        int[] dp = new int[n + 1]; // 해당 위치까지의 가장 많이 설치할 수 있는 전깃줄 개수
        int maxInstall = 1; //가장 많이 설치할 수 있는 개수

        for (int i = 1; i <= n; i++) {
            num[i][0] = sc.nextInt();
            num[i][1] = sc.nextInt();
        }

        //[][0] 정렬 (A 전봇대 기준으로)
        Arrays.sort(num, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (num[j][1] < num[i][1]) { // 과거 A의 전깃줄과 이어진 B 번호보다 현재 B 번호가 더 커야 이을 수 있다.(A보다큰) 
                    dp[i] = Math.max(dp[i], dp[j] + 1); // 과거 최대 전깃줄 개수 + 1 세팅
                }
            }
            maxInstall = Math.max(maxInstall, dp[i]); // 최대 전깃줄 개수 세팅
        }
        System.out.println(n - maxInstall); //없애야 하는 전깃줄의 최소 개수 = 전체개수 - 가장많이설치할 수 있는 개수
    }
}

 

 

추가로 저는 원래 for 반복문에서 이전에 풀었던 비슷한 dp 문제들 처럼 

for (int i = 1; i <= n; i++) {
            int max = 0;
            for (int j = 1; j < i; j++) {
                if (max < dp[j] && num[j][1] < num[i][1]) { // 과거 A의 전깃줄과 이어진 B 번호보다 현재 B 번호가 더 커야 이을 수 있다.(A보다큰)
                    max = dp[j];
                }
            }
            dp[i] = max + 1;
            maxInstall = Math.max(maxInstall, dp[i]); // 최대 전깃줄 개수 세팅
        }

이런식으로 풀었었습니다.  그러나 밑 블로그 분의 풀이를 참고하고 이분의 코드가 더 깔끔하고 정석인 것 같아 코드를 바꾸고 앞으로도 비슷한 문제가 나오면 이렇게 풀려고 합니다.

 

https://hooongs.tistory.com/archive/20200111

2020/01/11 글 목록

 

댓글과 공감은 큰 힘이 됩니다.