[BOJ] BOJ 2565번 '전깃줄' (Java)

[백준 2565번 '전깃줄']

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

 

[접근 방식]

스스로 해결하지 못한 문제.

 

다이나믹 프로그래밍과 최장 증가 부분 수열을 사용하여 해결하는 문제이다.

전기줄들을 A위치를 기준으로 오름차순 정렬한다.

정렬된 전기줄들의 B위치 배열에서 최장 증가 부분 수열의 최대 길이를 구한다.

 

전체 전기줄 개수에서 최대 길이를 빼면, 제거해야 하는 전기줄의 개수가 도출된다.

 

여기서 중요 포인트는, 최장 증가 부분 수열을 다이나믹 프로그래밍을 통해 구현하는 것이다.

length 배열의 정의 : length[i] 를 끝으로(포함) 하는 최장 증가 부분 수열의 길이

따라서 인덱스 k의 원소를 포함하는 최장 증가 부분 수열의 길이를 DP를 이용하여 구한다.

인덱스 k 원소가 가장 큰 수여야만 " 인덱스 k의 원소를 포함하는 최장 증가 부분 수열 "이 완성되게 된다.

 

[Java 코드]

  /**
   * BOJ_2565 전깃줄
   * https://www.acmicpc.net/problem/2565
   * keyword - 
   */

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

  public class Main {

    static class Edge {
      int start, end;
      public Edge(int start, int end) {
        this.start = start;
        this.end = end;
      }
    }

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

      //전기줄의 개수 : n
      int n = Integer.parseInt(br.readLine());

      //length[i]를 끝으로(포함) 하는 최장 증가 부분 수열의 길이 저장
      int[] length = new int[n];

      //A, B의 위치 정보를 저장할 전기줄 리스트
      List<Edge> edges = new ArrayList<>();

      //전기줄 입력
      for (int i = 0; i < n; i++) {
        String[] data = br.readLine().split(" ");
        int u = Integer.parseInt(data[0]);
        int v = Integer.parseInt(data[1]);
        edges.add(new Edge(u, v));
      }

      //A위치를 기준으로 오름차순 정렬
      Collections.sort(edges, (a, b) -> {
        return a.start - b.start;
      });

      //length 데이터 입력
      for (int k = 0; k < n; k++) {
        length[k] = 1; //자기 자신만 포함 - 1
        for (int i = 0; i < k; i++) {
          if (edges.get(i).end < edges.get(k).end) {
            length[k] = Math.max(length[k], length[i] + 1);
          }
        }
      }

      //b위치의 최장증가부분수열 길이 구하기
      int max = 0;
      for (int l : length) {
        max = (max > l) ? max : l;
      }

      //제거해야 하는 전기줄 개수 출력
      System.out.println(n - max);
    }
  }

 

 

[Rewind]

1.어려웠던 점

-문제의 해결방식을 스스로 찾아내지 못한 것이 아쉬움.

- 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)을 전혀 이해하고 있지 않음.

- 구현 방식 또한 이해하고 있지 않음.

 

2. 알게된 점

- 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)의 개념 / 구현방식을 알게됨.

 

3. 개선방안

- 문제를 해결하며 알게된 여러 개념들을 잊지말자.