[JAVA] 백준 2565 전깃줄

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

2565번: 전깃줄

 

- 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다.

- 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 

 

 

- A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 전깃줄 , A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 

 

- 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 이해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램

 

 

문제 풀이 

 

[ 백준 2565 ] 전깃줄 (C++) :: 얍문's Coding World.. (tistory.com)

[ 백준 2565 ] 전깃줄 (C++)

- 없애야 하는 전깃줄의 최소 개수 = N - 없앨 필요가 없는 전깃줄의 최대 갯수

- 없애지 않아도 되는 전깃줄의 최대 개수는 오른쪽 전봇대에서 "가장 긴 증가하는 부분수열"을 구하는 과정과 동일

 

 

1. 왼쪽 전봇대를 기준으로 정렬을 시켜준다.

2, 오른쪽 전봇대에서 "가장 긴 증가하는 부분 수열"을 구해준다.

3. 2번 과정에서 구한 "가장 긴 증가하는 부분 수열"의 크기를 N에서 빼준다. 

 

- 위의 블로그를 참고하여 코드 작성하여 제출하였으나 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;


public class Main {
	static int A;
	static int B;
    static int memo[];
    static int arr[];
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine()); //전깃줄 개수
        memo = new int[n];
        
        HashMap<Integer,Integer> map = new HashMap<>();
        

        for(int i=0; i<n; i++)
        { 
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	A = Integer.parseInt(st.nextToken());
        	B = Integer.parseInt(st.nextToken());
        	map.put(A,B);
        }
        
        //A를 기준으로 오름차순 정렬
        List<Integer> keyList = new ArrayList<>(map.keySet());
        keyList.sort((s1,s2)->s1.compareTo(s2));
        
        arr = new int[n]; //B를 담을 배열 
        int idx=0;
        
        for(Integer val : map.values())
        {
        	arr[idx++]=val;
        }
        
        for(int i=0; i<n;i++)
        {
        	memo[i] =1;
        	
        	for(int j=0; j<i; j++)
        	{
        		if(arr[j]<arr[i] && memo[i]<memo[j]+1)
        		{
        			memo[i] = memo[j]+1;
        		}
        	}
        }
        
        int max = -1;
        for(int i=0; i<n; i++)
        {
        	max = memo[i]>max? memo[i]:max;
        }
        
        int result = n-max;
        
        bw.write(result+"");
        bw.flush();
        bw.close();
        
        
    }
}

 

 

[백준] 2565번 : 전깃줄 - JAVA [자바] (tistory.com)

[백준] 2565번 : 전깃줄 - JAVA [자바]

 

- 최대한 설치 가능한 개수를 구하면 됨

 

- A 전봇대 기준으로 i번째에 연결된 전깃줄을 잇고 이후 전선들을 탐색하면서 i번째가 연결된 B의 값보다 큰 경우들을 모두 탐색 

- 결국 정렬된 A를 기준으로 B에 연결된 값들에 LIS를 하면 됨 

 

 

정답 

 

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


public class Main {
	static int A;
	static int B;
    static int memo[];
    static int arr[];
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine()); //전깃줄 개수
      
        int memo[] = new int[n];
        int input[][] = new int[n][2];
        
        
        for(int i=0; i<n;i++)
        {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	input[i][0] = Integer.parseInt(st.nextToken());
        	input[i][1] = Integer.parseInt(st.nextToken());
        }
        
        //A를 기준으로 정렬
        Arrays.sort(input, new Comparator<int[]>() {
        	@Override
        	public int compare(int[] o1, int[] o2) {
        		return o1[0] - o2[0];
        	}
        });
        
        for(int i=0; i<memo.length; i++)
        {
        	memo[i] = 1;
        	
        	//i번째 전봇대를 기준으로 이전의 전봇대들의 전선을 연결하기 위한 탐색
        	//i번째 전봇대에 연결된 B전봇대는 탐색할 j번째 전봇대에 연결된 B전봇대보다 값이 커야함
        	for(int j=0; j<i; j++)
        	{
        		if(input[i][1]>input[j][1])
        		{
        			memo[i] = Math.max(memo[i], memo[j]+1);
        		}
        	}
        }
        
        int max = 0;
        for(int i=0; i<n; i++)
        {
        	max = Math.max(max, memo[i]);
        }
       
        int result = n - max;
        bw.write(result+"");
       
       bw.flush();
       bw.close();
        
        
        
    }
}