[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)11053번, 가장 긴 증가하는 부분 수열

문제 링크

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

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

 

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

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

예제 1번일 때 표를 확인하면

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

10 = {10}

20 = {10, 20}

10 = {10}

30 = {10, 20, 30}

20 = {10, 20}

50 = {10, 20, 30, 50}

최대 숫자라고 생각하면 자신 앞에 있는 숫자들에서 자신보다 작은 수로 수열을 만드는 것입니다.여기서 규칙을 발견할 수 있습니다.위에 표에서 30을 보면 30앞에 있는 수 중에 작은 수들로 수열을 만들어야 하는데 메모이제이션을 사용하여 자기보다 작은 수 중에 가장 가까운 수에 +1을 하게되면 자신을 최대숫자로 하는 수열의 길이를 얻을 수 있습니다.30이었으니 앞에 작은 수 중 가장 가까운 수 2에 저장된 메모이제이션에 2+1 = 3으로 수열의 길이가 된다.50이면 30이 가장 가까운 수로 3+1 = 4가 수열의 길이가 됩니다.첫 번째 수를 최대 숫자라고 생각하면 무조건 수열의 길이는 1이 됩니다.

수열의 길이에 따른 수를 저장하기 위해  [수열의 크기]으로 메모이제이션을 구성하였습니다.

 

 

• 수열의 길이 값 저장할 메모이제이션 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 수열의 길이를 얻는 함수 seqCal을 만들었습니다.
• for문을 통하여 몇 번째 숫자를 최대 숫자로 하는 수열의 길이를 메모이제이션에 저장하였습니다. 
• for문을 통하여 메모이제이션에 저장된 수열의 길이중 Math.max를 사용하여 가장 긴 수열을 얻었습니다.
• System.out.println을 사용하여 가장 긴 수열의 길이를 출력하였습니다.

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

결과 코드

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());
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	num = new int[index];
    	check = new int[index];
    	int max = Integer.MIN_VALUE;                          
    	for(int i=0;i<index;i++)
    		num[i] = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<index;i++)
    		check[i] = seqCal(i);
    	
    	for(int i=0;i<index;i++)
    		max = Math.max(max, check[i]);	//최대 길이 구하기
    	
    	System.out.println(max);		//결과 출력
    	br.close();
	}
    //-----------수열 길이 구하는 함수---------
	public static int seqCal(int depth) {
		if(depth==0)
			return 1;
		int result = 1;
		for(int i=depth;i>=0;i--) {
			if(num[depth]>num[i] && result<=check[i]) {
				result =check[i]+1;
			}
		}
		return result;
		}

	}