[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)2565번, 전깃줄

문제 링크

2565번: 전깃줄

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

 

전깃줄에 대한 정의는 문제에서 모두 알려주고 있습니다.

문제에 대한 수열에서 각 숫자들이 최대 숫자라고 생각하고 수열에 길이를 만들어보면 표를 만들어보았습니다.

처음에 문제를 접근할 때에는 연결된 전깃줄에서 줄여나가는 방식으로 접근을 하였습니다. 그러다가 전깃줄을 처음부터 연결하는 방식으로 최대 연결한 개수를 구하는 것을 이용하면 정답에 가까워진다는 것을 깨닫고 전깃줄을 처음부터 연결하는 방식을 사용하였습니다.

각 전기줄이 연결하는데 마지막 전깃줄이라고 생각하고 교차하지 않고 각각의 최대한 연결할 수 있는 횟수를 구하였습니다.

문제에서는 전깃줄을 없앤 최소 수를 구하는 것으로 전체 전깃줄 - 최대 연결할 수 있는 전깃줄을 하면 전깃줄을 없앤 최소수를 구할 수 있습니다.

 

전깃줄에 개수에 따라 수를 저장하기 위해  [전깃줄의 개수]으로 메모이제이션을 구성하였습니다.

 

 

• 수열의 길이 값 저장할 메모이제이션 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 입력값에 전깃줄이 순서가 섞여있기 때문에 전봇대 A에 값을 기준으로 Comparator를 구성하여 정렬하였습니다.
• 전깃줄 연결 최대 개수를 얻는 함수 electricWire을 만들었습니다.
• for문을 통하여 메모이제이션에 저장된 연결되는 전깃줄 최대 수를 Math.max 이용하여 얻었습니다.
• 문제에서는 없앤 전깃줄의 최소값을 구해야 하기 때문에 전체 전깃줄 - 최대 연결된 전깃줄 수를 연산하였습니다.
• System.out.println을 사용하여 전깃줄 줄인 최소값을 출력하였습니다.

• 0인 경우 재귀를 반복하여 결과값을 메모이제이션에 저장한 뒤 반환한다.
• check가 0이 아니면 메모이제이션에 저장된 값이 있기에 그 값을 가져온다.
• 위에 알고리즘 설명을 토대로 재귀하도록 selectricWire함수를 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] check;		//메모이제이션 배열
	static int[][] num;		//전깃줄 저장 배열
	static int index;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //---------입력 값 저장 및 배열 초기화----------
    	index = Integer.parseInt(br.readLine());
    	num = new int[index][2];
    	check = new int[index];
    	int max = Integer.MIN_VALUE;
    	for(int i=0;i<index;i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    		num[i][0] = Integer.parseInt(st.nextToken());
    		num[i][1] = Integer.parseInt(st.nextToken());
    	}
    	//----------전깃줄 정렬-----------
    	Arrays.sort(num, new Comparator<int[]>() {
    		@Override
    		public int compare(int[] o1, int[] o2) {
    			return o1[0]-o2[0];
    		}
		});
    	//함수 실행 및 최대값 구하기
    	for(int i=0;i<index;i++) 
    		max = Math.max(electricWire(i), max);
    	
    	System.out.println(index-max);		//결과 출력
    	br.close();
	}
    //----------전깃줄 구하는 함수-------------
	public static int electricWire(int depth) {
		if(check[depth]==0) {
			check[depth]=1;
			for(int i=0;i<depth;i++) {
				if(num[depth][1]>num[i][1])
					check[depth] = Math.max(check[depth], electricWire(i)+1);
			}
		}
		return check[depth];
	}
}