[백준] 단계별로 풀어보기(단계:27, 동적 계획법과 최단거리 역추적,JAVA)14003번, 가장 긴 증가하는 부분 수열 5

문제 링크

14003번: 가장 긴 증가하는 부분 수열 5

---

주의사항

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

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

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 증가하는 수열 중 가장 긴 수열의 길이를 결과로 출력해야 합니다.

 

배열

 

sequence : 입력된 수열 값 저장하는 배열 

 

index : 해당 i값 미만의 증가하는 수열에서 가장 큰 길이 값 저장하는 배열

 

리스트

 

list : 메모이제이션 리스트

 

이 문제에서는 리스트를 이용해서 증가하는 수열을 만드는 방법을 사용하였으며 마지막에 리스트의 크기가 수열의 길이가 됩니다.

 

예제입력 1에 list의 값을 표로 살펴보면

1. 입력값 10일 때

10

 

2. 입력값 10일 때

10

20

리스트의 마지막 값 10보다 20이 크므로 증가하는 수열에 포함되어 리스트에 추가하였습니다.

 

3. 입력값 10일 때

10

20

리스트의 마지막 값 20보다 입력값 10이 작아서 증가하는 수열 마지막 값으로 추가할 수 없습니다.

하지만 10을 빨간색으로 표시한 이유는 입력값 10이 증가하는 시작수열로 변경될 수 있기 때문에 바뀌지 않은 것처럼 보이지만 실제로는 바뀐것으로 이해하고 있어야 합니다.

4. 입력값 30일 때

10

20

30

리스트의 마지막 값 20보다 30이 크므로 증가하는 수열에 포함되어 리스트에 추가하였습니다.

5. 입력값 20일 때

10

20

30

리스트의 마지막 값 30보다 입력값 20이 작아서 증가하는 수열 마지막 값으로 추가할 수 없습니다.

하지만 10을 빨간색으로 표시한 이유는 입력값 10이 증가하는 시작수열로 변경될 수 있기 때문에 바뀌지 않은 것처럼 보이지만 실제로는 바뀐것으로 이해하고 있어야 합니다.

 

6. 입력값 50일 때

10

20

30

50

리스트의 마지막 값 30보다 50이 크므로 증가하는 수열에 포함되어 리스트에 추가하였습니다.

 

증가하는 수열의 길이는 리스트의 크기인 4를 결과로 출력하면 됩니다.

 

10과 20이 동일하게 들어갔을 때 바뀐것으로 이해해야 한다는 것을 예시로 설명하겠습니다.

만약 입력값이 {100, 200, 3} 을 받았을때 200까지는 아래와 같은 리스트일 것입니다.

100

200

여기서 숫자 3을 입력 받았을 때 리스트가 변경됩니다.

3

200

100, 200, 3에서 가장 긴 증가하는 수열은 {100, 200} 이지만 위에 리스트를 보면 {3, 200}처럼 보입니다.

리스트에서는 원래의 값이 있었기 때문에 3보다 크고 200보다 작은 값이 원래 하나 존재한다고 생각하시고 있으시면 될 것 같습니다.

3 ≤ 100 ＜200 으로 리스트에 3의 값에는 100까지 존재한다고 생각하시고 계시면 됩니다.

리스트의 값을 변경할 때 브루트포스로 저장된 리스트의 값을 비교하여 변경해도 되지만

이 문제에서는 브루트 포스로 작성했을 때 시간 초과가 발생하여 이분탐색을 이용하여 리스트를 변경하였습니다.

 

가장 긴 증가하는 수열을 결과로 출력할 때에는 index[]배열을 이용하여 출력합니다.예제입력 1에 index배열을 표로 살펴보면(최대 길이 : 4)

10	20	10	30	20	50
1	2	1	3	2	4

최대 길이부터 1이 될 때까지 index에 해당하는 값을 순서대로 Stack에 저장한 뒤 출력하였습니다.

최대 길이가 4일 때 Stack

50(index = 4)

최대 길이가 3일 때 Stack

30(index = 3)

50

최대 길이가 2일 때 Stack

20(index = 2)

30

50

최대 길이가 1일 때 Stack

10(index = 1)

20

30

50

Stack은 LIFO(후입선출)의 형태로써 Stack에 저장된 값들을 순서대로 출력하면

가장 긴 증가하는 수열 : 10 20 30 50

수열의 값들을 결과로 출력할 수 있습니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값을 받아서 list에 규칙에 맞게 구성합니다.

2. list를 구성할 때에는 이분 탐색 UnderBound를 사용하여 구성합니다.

3. list의 크기가 가장 긴 증가하는 수열의 길이로써 결과로 출력합니다.

4. 가장 긴 증가하는 수열의 값들을 Stack과 index를 사용하여 증가하는 수열의 값을 출력하였습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 입력되는 수열의 값을 분리하였습니다.
• 위에 설명한 내용을 바탕으로 입력된 수열 값 list에 저장 및 수정을 진행합니다.
• list를 저장 및 수정할 때 반복문과 UnderBound를 사용하여 실행하도록 하였습니다.
• BufferedWriter에 list.size()로 증가하는 수열의 최대 길이를 저장하였습니다.
• Stack과 index를 이용하여 증가하는 수열의 값의 형태를 만들었습니다.
• BufferedWriter에 Stack에 저장된 수열의 값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

import java.io.*;
import java.util.*;
public class Main{
	static int N;
	static int[] index,sequence;	//해당 인덱스 최대 길이 저장 배열, 입력 수열값 저장 배열
	static ArrayList<Integer> list = new ArrayList<Integer>();	//메모이제이션 리스트
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //----배열 초기화------
    	N = Integer.parseInt(br.readLine());
    	sequence = new int[N+1];
    	index = new int[N+1];
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	list.add(-1000000001);		//수열의 값이 가장 작은 값보다 작은 값을 추가
    	for(int i=1;i<=N;i++) {
        	//입력값 수열 저장
    		int num = Integer.parseInt(st.nextToken());
    		sequence[i] = num;
            	//리스트 마지막 값보다 값이 클 경우
    		if(list.get(list.size()-1)<num) {
    			list.add(num);		//리스트에 추가
    			index[i] = list.size()-1; 
    		}else {		//리스트 마지막 값보다 작을 경우
            		//UnderBound 이분탐색 진행
    			int start = 1;
    			int end = list.size();
    			while(start<end) {
    				int median = (start + end)/2;
                    		//중간값 입력값보다 작을 경우
    				if(list.get(median) < num)
    					start = median + 1;
    				else	//중간값 입력값보다 크거나 같을 경우
    					end = median;
    			}
    			list.set(end, num);		//list 변경
    			index[i] = end;
    		} 		
    	}
    	int length = list.size()-1;		//수열의 최대 길이 저장
    	bw.write(length + "\n");		//최대 길이 BufferedWriter 저장
    	Stack<Integer> stack = new Stack<Integer>();
    	//Stack과 index를 통해 수열의 값 BufferedWriter 저장
    	for(int i=N;i>0;i--) {
    		if(index[i] == length) {
    			stack.add(sequence[i]);	
    			length--;
    		}
    	}
    	while(!stack.isEmpty())
    		bw.write(stack.pop() + " ");
    	
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
}