[백준] code.plus(다이나믹 프로그램 part 1,JAVA)14002번, 가장 긴 증가하는 부분 수열 4

문제 링크

14002번: 가장 긴 증가하는 부분 수열 4

---

주의사항

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

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

---

문제 설명

---

접근 방법

다이나믹 프로그램

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

 

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

 

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

 

이 문제에 핵심은

1. 입력값에서 가장 길이가 긴 증가하는 수열을 만들어야 한다.

2. 가장 긴 수열의 길이와 해당 수열을 결과로 출력해야한다.

3. 수열이 여러개여도 아무거나 출력하면 된다.

 

배열

 

DP : 메모이제이션 배열

 

num : 수열에 들어갈 수 있는 입력값 숫자 저장 배열

 

 

DP 배열과 num을 이용하여 가장 길이가 긴 증가하는 수열을 구하였습니다.

 

DP[i]는 i이하의 입력값에서 만들 수 있는 증가하는 수열의 최대 길이를 표현합니다.

 

DP의 값을 예제입력 1에 입력값에 대한 표로 나타낸다면

	1	2	3	4	5	6
DP	1	2	1	3	2	4
입력값	10	20	10	30	20	50

 

여기서 규칙을 발견할 수 있습니다.

DP[i]의 값보다 작은 DP값 중에서 입력값이 작으면서 가장 큰 값 + 1을 해주는 것이 DP[i]의 값이 됩니다.

 

DP[2]를 구할 때

DP[i]에서 i가 2보다 작은 DP값중 입력값이 작으면서 가장 큰 값 + 1

DP[1]은 DP[2]보다 작은 10이고 DP값이 가장 큰 값으로

DP[2] = DP[1] + 1 = 1 + 1 = 2

 

DP[4]를 구할 때

DP[i]에서 i가 4보다 작은 DP값중 입력값이 작으면서 가장 큰 값 + 1

DP[2]는 DP[4]보다 작은 20이고 DP값이 가장 큰 값으로

DP[4] = DP[2] + 1 = 2 + 1 = 3

 

위 경우를 반복하여 DP를 구성한 뒤 DP값 중 가장 큰 값이 최대 길이가 됩니다.

 

이제 길이를 구하였다면 결과를 출력할 때에 저는 Stack을 사용하였습니다.

 

Stack은 후입선출 형태로 DP의 값이 최대값부터 1이 될 때까지 입력값을 Stack에 저장한 뒤 출력하면

 

수열의 형태로 출력할 수 있습니다.

 

위에 표에서 최대 길이는 4입니다.

 

DP의 값이 4인 입력값을 Stack에 저장

DP의 값이 3인 입력값을 Stack에 저장.....을 반복하면

Stack에는 아래에 표처럼 저장됩니다.

10

20

30

50

Stakc은 후입선출로 순서대로 출력하게 되면 결과는

{10, 20, 30 50}으로 출력되어 수열의 형태로 결과를 출력할 수 있습니다.

 

문제에 해결알고리즘은

1. 입력값을 받아서 규칙을 적용해서 DP[]를 구성합니다.

2. DP[]를 구성할 때 최대 길이도 구합니다.

3. Stack의 후입선출을 이용하여 수열의 형태를 만듭니다.

4. 수열의 길이와 수열의 형태를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 통해 입력값을 저장하였습니다.
• DP 및 수열 최대 길이를 구하는 sequence함수를 만들었습니다.
• Stack에 DP에 저장된 값이 최대길이부터 내림차순으로 해당하는 입력값을 저장하였습니다.
• BufferedWriter에 최대 길이와 스택에 저장된 값을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• sequence는 반복문을 통해 위에 설명한 규칙을 적용시켜주었습니다.

 

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N,result = 0;
	public static int[] num,DP;		//입력값 저장 배열, 메모이제이션 배열
	public static StringBuilder sb = new StringBuilder();	//수열 저장
    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());
    	num = new int[N+1];
    	DP = new int[N+1];
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	for(int i=1;i<=N;i++) 
    		num[i] = Integer.parseInt(st.nextToken());
    	
    	sequence();		//함수 실행
    	bw.write(result + "\n");		//최대 길이 BufferedWriter 저장
    	Stack<Integer> stack = new Stack<Integer>();	//수열 값 얻기 위한 스택
    	for(int i=N;i>0;i--) {
    		if(DP[i] == result) {	//최대 길이부터 스택에 입력값 저장
    			stack.add(num[i]);
    			result--;
    		}
    		if(result==0)
    			break;
    	}
    	int size = stack.size();
    	for(int i=0;i<size;i++) {
    		bw.write(stack.pop() + " ");	//수열 BufferdWriter 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //-------DP 구성 및 수열 최대 길이 구하는 함수------
    public static void sequence() {
    	for(int i=1;i<=N;i++) {
    		for(int j=i;j>=0;j--) {
    			if(num[i]> num[j]) {
    				DP[i] = Math.max(DP[i], DP[j]+1);
    				result = Math.max(result, DP[i]);
    			}
    		}
    	}
    	return;
    }
}