[백준] 2565 : 전깃줄

문제 출처: https://www.acmicpc.net/problem/2565

---

문제

---

시도

문제 등급이 실버이든 골드이든 동적 계획법 문제는 점화식과 메모이제이션에 대한 감이 안 잡혀서 항상 난처함만 더해갔다.

---

풀이

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

public class Main {
    
    
    static Integer[] dp;
    static int[][] wire;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        
        dp = new Integer[N];
        wire = new int[N][2];
        
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            
            wire[i][0] = Integer.parseInt(st.nextToken());
            wire[i][1] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(wire, 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);
        }
        
        System.out.print(N - max);
    }
    
    static int recur(int N) {
        // 탐색하지 않았던 위치라면
        if(dp[N] == null) {
            dp[N] = 1;
            
            // A의 N번째와 이후의 전봇대들 비교
            for(int i = N+1; i < dp.length; i++) {
                if(wire[N][1] < wire[i][1]) {
                    dp[N] = Math.max(dp[N], recur(i) + 1);
                }
            }
        }
        return dp[N];
    }
}

 

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

---

알게 된 점

1. int 배열 초기화 시 특정 값으로 전부 초기화 할 때 항상 불필요한 for문을 추가적으로 돌렸었는데 이번 풀이를 통해 Integer 배열을 씀으로써 null 체커를 활용하는 방법을 배웠다.

2. Comparator를 사용한 정렬을 기억해야겠다.