(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 2565 전깃줄 (골드 5)

이제 동적 계획법도 얼마 남지 않았다.

이번 문제는 양 쪽의 전봇대에 전깃줄이 교차하지 않도록 없애야 하는 전깃줄의 최소 갯수를 출력하는 문제이다.

점화식을 어떻게 만들지가 좀 어려운 문제였는데 어떤 식으로 풀었는지 살펴보자.

---

어떻게 구해야 할까?

이번 문제의 핵심은 점화식을 어떻게 만들것인가가 핵심이었다.

처음 생각했을때는 1차원 배열 2개를 만들어 각각의 전봇대의 숫자를 넣은 후, A 전봇대를 기준으로 하여 반복문을 돌린 후  B 전봇대의 값이 이전 인덱스의 최대 값 보다 높으면 카운트를 추가하는 형식으로 구현하려고 하였다.

예를 들어서 예제를 기준으로 보자.

0	1	2	3	4	5	6	7	8	9
1	2	3	4	5	6	7	8	9	10
8	2	9	1		4	6		7	10

A 전봇대를 기준으로 하면 다음과 같이 값이 들어오게 될 것이다.

교차가 된다는 말은 현재 전봇대의 값이 이전 값보다 작은 값이 들어왔다는 말과 동일하므로 그런식으로 로직을 구성하면 되지 않을까 생각을 했었는데, 코드로 막상 구현을 해보니 마음처럼 잘 되지 않았다.

문제가 된 것이 여러부분 있었는데,

1. 문제에서는 전봇대의 갯수가 아니라 전깃줄의 개수가 주어지므로 전봇대를 기준으로 배열을 만들수 없다.
2. 입력 순서는 랜덤하게 들어오므로 1차원 배열로는 위의 방법이 불가능 하다.
3. 입력순서 대로 전깃줄 만큼 크기를 만든다 하더라도 현재의 로직으로는 아래로 교차하는 경우만 알 수 있다. (즉, B에 대해서 한번 더 검증을 하여야한다)

따라서, 우선 나는 전깃줄의 갯수만큼 2차원 배열을 만들어 값을 담은 후 A 를 기준으로 정렬하고 Top-Down 방식을 통하여 구현을 해보고자 하였다.

로직은 다음과 같다.

import java.io.*;
import java.util.*;

class Main {
    public static int n,result;
    public static int[][] arr;
    public static Integer[] dp;
    public static StringTokenizer st;

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

        dp[0] = 0;

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

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

    }

    public static int cal(int a) {
        if (dp[a] == null) {

            dp[a] = 1;
            
            for (int i = a + 1; i < n; i++) {
                if (arr[a][1] < arr[i][1]) {
                    dp[a] = Math.max(dp[a], cal(i) + 1);
                }
            }
        }

        return dp[a];
    }

}

잘 작동할거라 생각했으나 결과는 실패... 이런 저런 실험을 계속 해보다가, 아예 다른 방법을 시도해 보기로 하였다.

---

잘못된 것은 전체 - 바른 것의 값과 같다!

어차피 우리가 구해야 하는 것은 교차된 전깃줄의 최소값이다.

즉, 전체값 - 교차하지 않은 전깃줄의 최대값과 동일한 것이다.

그렇게 생각을 바꾸니 좀더 문제가 심플해 보이기 시작했다.

각 인덱스별로 계산을 하도록 재귀문을 변경하였는데, 특정 인덱스 a가 들어오면 해당 인덱스 +1 부터 전체 수 만큼 반복하면서 해당 인덱스의 값보다 큰 값이 있는지 검증한다.

만일 큰값이 있다면 다시 재귀로 해당 인덱스의 값을 가져와 +1 한값을 초기값과 비교해 주면 최종적으로 해당 배열에서 교차하지 않는 전깃줄의 최대값을 구할 수 있다.

따라서, 나는 로직을 다음과 같이 변경하였다.

import java.io.*;
import java.util.*;

class Main {
    public static int n,result;
    public static int[][] arr;
    public static Integer[] dp;
    public static StringTokenizer st;

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

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

        result = 0;

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

    }

    public static int cal(int a) {
        if (dp[a] == null) {

            dp[a] = 1;

            for (int i = a + 1; i < n; i++) {
                if (arr[a][1] < arr[i][1]) {
                    dp[a] = Math.max(dp[a], cal(i) + 1);
                }
            }
        }

        return dp[a];
    }

}

우선 2차원 배열을 선언하고, 각각의 인덱스에 입력값을 넣는다.

그 후, A 전봇대에 해당하는 0번 배열을 기준으로 배열을 정리한다.

int[]의 정렬이 필요하기에 Comarator를 Override하면서 직접 작성해 주었다.

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

그 후, 반복문을 돌면서 채워 나가는데 반복문을 돌때마다 최종 값인 Result와 비교하며 최대값을 가져오게 한 후, 마지막에 전체값 n - Result를 통하여 결과를 출력하였다.

 

문제에만 집중하였을 때는 어떻게 짜야할 지 잘 보이지 않았는데 뒤집어 생각해보니 생각보다 간단한 문제였던거 같다.