[백준] code.plus(다이나믹 프로그램 part 2,JAVA)11722번, 가장 긴 감소하는 부분 수열

문제 링크

11722번: 가장 긴 감소하는 부분 수열

---

주의사항

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

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

---

문제 설명

---

접근 방법

다이나믹 프로그램

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

 

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

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

 

이 문제에 핵심은

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

 

배열

 

DP : 메모이제이션 배열

 

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

 

DP[]와 sequence 배열을 이용하여 가장 긴 감소하는 수열의 길이를 구하였습니다.

 

DP[i]의 값은 i번째 미만이면서 sequence[i]보다 큰 수열 값 중 DP값이 가장 큰 수 + 1의 값입니다.

예제 입력1의 DP표를 표현하면

10	30	10	20	20	10
1	1	2	2	2	3

DP[3]을 확인해보면

DP[1~2]에서 10보다 큰 수열 값에서 가장 큰 DP값은 DP[2](30)입니다.

 

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

 

DP[5]을 확인해보면

DP[1~4]에서 20보다 큰 수열 값에서 가장 큰 DP값은 DP[2](30)입니다.

 

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

 

DP[6]을 확인해보면

DP[1~5]에서 10보다 큰 수열 값 중에서 가장 큰 DP값은 DP[5]입니다.

 

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

 

결과로 가장 길이가 긴 값을 출력해야 하기 때문에 DP값 중에서 가장 큰 값을 출력합니다.

 

가장 큰 값 3을 결과로 출력합니다.

 

문제에 해결알고리즘은

1. DP[1]의 값을 1으로 초기화해줍니다.

2. 규칙을 적용하여 DP[]를 구성합니다.

3. DP의 최대값을 구해서 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer을 통해 입력되는 수열 값을 분리하였습니다.
• DP[1]의 값을 1로 초기화해주었습니다.
• 규칙을 적용하여 DP를 구성하고 최대 길이를 반환하는 cal함수를 만들었습니다.
• BufferedWriter에 최대 길이를 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• cal은 반복문을 통해 위에 설명한 규칙을 적용시켜주었습니다.
• cal은 DP를 구성하고난 뒤에 최대 길이를 결과로 반환하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int N;
	static int[] DP,sequence;	//메모제이션 배열, 수열 저장 배열
    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());
    	DP = new int[N+1];
    	sequence = new int[N+1];
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	for(int i=1;i<=N;i++) 
    		sequence[i] = Integer.parseInt(st.nextToken());
    	DP[1] = 1;		//DP[1]을 1으로 초기화
    	int result = cal();	//DP구성하는 함수 실행
    	bw.write(result + "\n");	//최대 길이 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }    	  
    //규칙을 통해 DP를 구성 및 최대 길이 반환하는 함수
    static int cal() {
    	int result = 1;
    	for(int i=1;i<=N;i++) {
    		for(int j=i-1;j>=1;j--) {
    			if(sequence[i]<sequence[j]) {	//규칙 적용
    				DP[i] = Math.max(DP[i], DP[j] + 1);
    				result = Math.max(DP[i], result);
    			}    			
    		}
    		if(DP[i] == 0)	//해당 값이 수열의 첫 번째 값일 때
    			DP[i] = 1;
    	}
    	return result;		//최대 길이 반환
    }
}