https://www.acmicpc.net/problem/2565
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
코드설명
DP 의 LIS 문제입니다.
문제 로직입니다.
DP[N] 은 N번쨰 위치에서 최대의 전기줄 개수입니다.
우리가 궁극적으로 구하는것은 ( 전체 전깃줄 개수 - 최대 연결전깃줄(max) ) 로써, 없애야하는 전깃줄의 최소 개수입니다.
1. 먼저 전봇대 A의 오름차순 순서로 정렬합니다. 이떄 Arrays.sort 람다식을 활용합니다.
2. LIS를 구합니다. 이 문제에서 가장 긴 증가하는 부분 수열(LIS)을 구하는 이유는, 전깃줄이 겹치지 않으면서 가장 긴 전깃줄의 개수를 구하면 답을 구할 수 있기에 그렇습니다.
예시와 함께 설명해보겠습니다.
전봇대 A의 1번위치와 1번위치가 연결되었다고 가정합니다. DP[1] = 1 입니다. 전봇대 A의 1번 위치에서 1개의 전봇대가 최대입니다.
이제 전봇대 A의 2번위치와 7번 위치가 연결되었다고 가정합니다. DP[2] = 2 입니다. 전봇대 A[1] 보다 전봇대A[2]가 7로써 더 크기에 전깃줄이 겹치지 않습니다.
전봇대 A[3] 번위치가 3번과 연결되었다고 가정합니다. DP[2] = 2 입니다. 전봇대 A[2] 는 A[3]과 겹치기에 A[2]를 제거했다고 가정합니다. DP[3] = 2 라는 의미는 3번쨰 전봇대의 기준에서 달 수 있는 가장 많은 전봇대입니다.
마지막에는 처음에 언급했듯
없애야하는 전깃줄의 최소 개수 = (전체 전깃줄 개수) - (최대로 연결될 수 있는 전깃줄) 를 출력합니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int N, M; public static int answer = 0; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); int[] dp = new int[N]; int[][] arr = new int[N][2]; 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, (o1, o2) -> o1[0] - o2[0]); for(int i=0;i<N;i++) { dp[i] = 1; //최소 개수인 1 로 초기화 for(int j=0;j<i;j++) { if(arr[i][1] > arr[j][1]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } int max = 0; for(int i=0; i<N;i++) { max = Math.max(max, dp[i]); //최대 전선개수 } System.out.println(N - max); } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 5557 1학년 - DP JAVA (0) | 2023.10.27 |
---|---|
[백준] 2011 암호코드 - DP JAVA (0) | 2023.10.26 |
[백준] 2302 극장 좌석 - 동적계획법(DP, Dynamic Programming) + 수학(Math) JAVA (0) | 2023.10.24 |
[백준] 1495 기타리스트 - 동적계획법(DP, Dynamic Programming) JAVA (0) | 2023.10.23 |
[백준] 15989 1, 2, 3 더하기 4 - DP JAVA (0) | 2023.10.22 |