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

문제 본문

동적 프로그래밍이란

동적 프로그래밍 방법은 문제의 해결 과정에서 이전에 구했던 과정을 또 다시 반복하여 실행되는 것을 방지하는 방법으로, 불필요한 코드 실행이 줄어 시간을 단축시킬 수 있습니다. 하지만 O(n)의 메모리가 할당 되어야 합니다.

 

문제 해설

전깃줄은 백준 사이트에서 LIS(Longest Increasing Subsequence)의 응용으로 분류된 문제입니다. N개의 전깃줄을 겹치지 않게 제거해야 하는 최소 개수의 전깃줄을 구해야 합니다. 문제 설명 그대로 풀려고 해서 방법이 도저히 생각나지 않다가 사람들의 힌트를 보고 깨달았습니다. ㅎ.. 해답은 제거가 아니고 설치입니다. 최소 개수의 전깃줄을 제거하여 겹치지 않게 설치된 남은 전깃줄은 겹치지 않게 설치될 수 있는 최대 전깃줄 입니다.
500
힌트와 참고 자료에서는 랜덤으로 들어오는 전깃줄의 위치 중 한 곳을 정하여 오름 차순 정렬을 시도하라고 하였지만, 해당 방법으로는 이중 배열 형태로 전깃줄의 값을 저장해야 할 것 같아 복잡해 보였습니다. 그래서 저는 전깃줄의 한 쪽 위치를 배열의 인덱스로 설정하고 이 후 입력되는 전깃줄의 위치를 해당 인덱스에 저장하는 방식으로 오름차순 형태를 구현했습니다. 다만 이 방법은 불필요한 메모리 낭비와 불필요한 반복 실행을 하게 되어서 더 좋은 방법을 고민하셔도 될 듯 합니다.

 

전체 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] line = new int[500 + 1];
        int maxLine = 0;

        for (int i = 0; i < n; i++) {
            int index = scanner.nextInt();
            int value = scanner.nextInt();

            maxLine = Math.max(maxLine, index);
            maxLine = Math.max(maxLine, value);

            line[index] = value;
        }

        int[] saveLength = new int[maxLine + 1];

        for (int index = 1; index <= maxLine; index++) {
            for (int range = 0; range < index; range++) {
                if (line[index] > line[range]) {
                    saveLength[index] = Math.max(saveLength[index], saveLength[range] + 1);
                }
            }
        }
        int result = 0;

        for (int index = 1; index <= maxLine; index++) {
            result = Math.max(saveLength[index], result);
        }

        System.out.println(n - result);
    }
}

 

 

코드 설명 - 값 저장

//만약 이 방법으로 하지 않고 오름차순 정렬로 진행 하게 된다면 메모리는 O(n)만 필요하게 됩니다.
//또 이 방법은 만약 존재하는 전깃줄의 위치가 1이랑 500이라면
//1 ~ 500번의 LCS를 확인하는 불필요한 반복문이 실행 되는 단점이 있습니다.

        int[] line = new int[500 + 1];
        int maxLine = 0;

        for (int i = 0; i < n; i++) {
            int index = scanner.nextInt();
            int value = scanner.nextInt();

            maxLine = Math.max(maxLine, index);
            maxLine = Math.max(maxLine, value);

            line[index] = value;
        }

전깃줄의 처음 들어오는 입력의 값을 배열의 인덱스로 저장했기 때문에 입력으로 들어올 수 있는 최대 위치인 500개의 공간(O(500))이 있어야 합니다.
maxLine은 전깃줄이 닿지 않는 최대 위치의 값을 구하고 그 지점까지만 LCS를 구하기 위해서 입니다.

 

 

코드 설명 - 동적 프로그래밍을 이용한 LCS 계산

 int[] saveLength = new int[maxLine + 1];

        for (int index = 1; index <= maxLine; index++) {
            for (int range = 0; range < index; range++) {
                if (line[index] > line[range]) {
                    saveLength[index] = Math.max(saveLength[index], saveLength[range] + 1);
                }
            }
        }

line 배열 인덱스에는 반대편에 연결되는 전깃줄의 위치 값이 저장되어 있습니다. 그리고 saveLength배열에는 각 인덱스마다 0에서 자신의 이전 인덱스까지 최대로 놓을 수 있는 전깃줄의 수(LCS)가 저장됩니다. 전깃줄을 설치할 수 있다는 것은 겹치지 않다는 것이고 겹치지 않다는 것은 이전 인덱스가 가리키는 위치가 내가 가리키는 위치보다 낮다는 것입니다.

 

o(n^2)의 시간 복잡도를 가진 LCS 과정을 거치면 saveLength에서 최대로 설치할 수 있는 전깃줄의 수를 구하고 전깃줄의 총 개수에서 빼면 답이 됩니다.

 

 

참고

• dp로 푸는 방법
• 문자열 LCS