[백준알고리즘-JAVA]2565번 풀이(전깃줄) - 초보도 이해하는 풀이
안녕하세요
인포돈 입니다.
백준 알고리즘 2565번 풀이입니다.
* 참고사항
- 개발환경은 eclipse을 기준으로 작성되었습니다.
- java언어를 이용하여 문제를 풀이합니다.
- 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
- 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.
백준 2565 (전깃줄)
문제
두 전봇대 A와 B 사이에 하나둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.
예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.
< 그림 1 >
전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.
출력
첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.
입력 예시
8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6출력 예시
3성공 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
static int N ;
static int[][] ele;
static Integer[] dp;
static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());;
ele = new int[N][2];
dp = new Integer[N];
for(int i = 0 ; i < N ; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
ele[i][0]=Integer.parseInt(st.nextToken());
ele[i][1]=Integer.parseInt(st.nextToken());
}
Arrays.sort(ele, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
for(int i = 0 ; i < N ; i ++) {
max = Math.max(electronic(i), max);
}
System.out.println(N-max);
}
public static int electronic(int num) {
if(dp[num]==null) {
dp[num]=1;
for(int i = num+1 ; i < dp.length ; i ++) {
if(ele[num][1] < ele[i][1])
dp[num]=Math.max(dp[num], electronic(i)+1);
}
}
return dp[num];
}
}전깃줄 알고리즘의 핵심은 바로 정렬입니다. 정렬을 하지 않고도 알고리즘을 풀이할 수 있겠지만, 대단히 어려워지는 문제가 될 것입니다.
해당 문제는 LIS의 문제를 살짝 응용한 문제입니다.
LIS기본적인 문제는 - 11053 (가장 긴 증가하는 부분 수열)이라고 볼 수 있고요
이전에 풀어보았던 가장 긴 바이 토닉 부분 수열(11054)의 경우는 LIS문제의 응용 편이라고 볼 수 있듯이
전깃줄은 LIS문제에 정렬을 합쳐놓은 문제입니다. 사실상 정렬을 해준다면, 그냥 기본 LIS문제를 풀듯이 풀면 끝!
STEP을 따라가며 이해해 봅시다.
알고리즘 흐름도
입력받기 -> 정렬하기 -> 재귀 하기 -> 출력하기
STEP1 문제를 이해하고 어떻게 풀이할지 찾아보기
이전에 말했던 방법을 잊어보고 처음으로 문제를 접했다면, 저희는 나름대로 DP문제처럼 재귀를 통해 DP에 어떤 값을 넣을지 고민하고 있을 것입니다.
저 같은 경우 DP를 각 인덱스에서 가질 수 있는 최대 전깃줄 개수로 생각했었습니다.
그러나 문제를 풀다 보니, 숫자가 일정하게 들어오는 것이 아닌, 마음대로 입력이 들어옴을 알 수 있었습니다. 그래서 그런지 재귀에 반복문을 사용해 봐도 올바르지 않게 실행됨을 알 수 있었습니다.
그러다 생각이 들었죠. 어차피 숫자는 정해져 있고, 우리는 최댓값만 찾으면 되기 때문에 임의로 내가 짝만 맞추고 A, B 둘 중 편한 걸로 순서를 정해서 풀어보기로 하였고 결론적으로 옳은 선택이 되었습니다.
물론 처음에 생각나지 않으실 수도 있습니다. 많이 풀어보세요 그게 답입니다.
그렇다면 이제 정렬을 구현해봐야겠죠. 다음으로 GO GO
STEP2 정렬 구현하기
정렬을 하기 전에 저희는 입력을 2차원 배열로 받아야 합니다. 왜냐하면 저희는 짝까지 바뀌면 안 되기 때문에 각각 다른 배열에 선언하기보다는 2차원 배열을 이용하여 1열을 기준으로 정렬해 주도록 합니다.
Arrays.sort(ele, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});2차원 배열 정렬을 잘 모르시는 분들께 설명해 드리겠습니다.
Arrays.sort메서드에는 저희가 보통 1차원 배열을
Arrays.sort(ele) 이런 식으로 입력을 넣어주죠
그러나 인자로 2차원 배열과, new Comparator객체를 넣어주면 2차원 배열을 정렬해 주죠
이때 사용된 것은 선언과 동시에 compare메서드를 override 하여 내가 원하는 방식으로 정렬하도록 합니다.
여기서 o1과 o2는 무엇이냐?
바로 각 행들을 의미합니다. sort메서드는 입력받은 ele (2차원 배열)을 지지고 볶아서 compare에 o1과 o2로 행들을 차례로 대입하여 줍니다.
그리고 반환 값으로 음수가 반환된다면 o2가 큰 값이 됨으로 순서가 바뀌지 않고 양수가 된다면 o1과 o2의 자리를 바꿔주는 작업을 대신해준답니다.
이해가 안 되시는 분들을 위해 입력 예시로 간략히 셜 명해 드리겠습니다.
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6
1 8과 3 9가 바로 o1 [], o2 [] 이게 됩니다.
그렇다면 return 1 - 3 = -2 가 반환되겠죠?
그렇다면 이제 순서는 바뀌지 않게 되죠. 이처럼 모든 행들을 비교하여 알아서 순서를 재배열해준답니다.
STEP 3 재귀 구현하기
public static int electronic(int num) {
if(dp[num]==null) {
dp[num]=1;
for(int i = num+1 ; i < dp.length ; i ++) {
if(ele[num][1] < ele[i][1])
dp[num]=Math.max(dp[num], electronic(i)+1);
}
}
return dp[num];
}뭐 이제 다들 여기까지 동적 계획법을 푸셨다면, 아주 기본적인 코드임을 알 수 있습니다. 앞서 저희는 정렬을 해주었습니다. 그렇다면 입력 예시로 들어온 값들은 아래와 같이 변해있겠죠
1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10그러면 완벽한 이해를 돕기 위해서 하나씩 진행해보겠습니다.
- 인자로 0이 들어온다.
- dp [0]은 null임으로 첫 번째 if문을 통과한다.
- dp [0]에 1을 넣는다.
- 이제 반복문을 통해 2 ~ 8까지 반복한다.
- ele [0][1] < ele [2 ~ 8][1]을 모두 비교한다. (이에 해당하는 값은 9와 10)
- dp [0] = Math.max(dp [0], electronic(2)+1)을 진행한다. 결론적으로 dp [0]은 3이 된다.
- eletronic(2)의 경우 electronic(7)로 을 수행하게 되고 electronic(7)은 1을 반환한다. 결론적으로
- eletronic(2)는 2를 반환하고 dp [0] = Math.max(dp [0], 3)을 비교한다. (이전에 dp [0]에는 1이 들어있다)
(3이 되는 이유는 1 3 10이 전깃줄로 이어지기 때문)
이런 식으로 인자를 0에서부터 7까지 모두 넣어준다면 전깃줄 문제는 쉽게 해결할 수 있습니다.
(관건은 정렬을 생각했는지 못했는지이다)