[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)11054번, 가장 긴 바이토닉 부분 수열

문제 링크

11054번: 가장 긴 바이토닉 부분 수열

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

 

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

예제 1에 대한 수열에서 각 숫자들이 중간에 기준이되는 수로 생각하면 왼쪽에 올 수 있는 수의 개수와 오른쪽에 올 수 있는 개수를 표로 만들어보았습니다.

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

 

왼쪽에 올 수 있는 수

1	5	2	1	4	3	4	5	2	1
0	1	1	0	2	2	3	4	1	0

1 = { }    5 =  {1 }    2 = {1}    1 = { }    4 = {1, 2}    3 = {1, 2}    4 = {1, 2, 3}

5 = {1, 2, 3, 4 }    2 = { 1 }    1 = { }

 

오른쪽에 올 수 있는 수

1	5	2	1	4	3	4	5	2	1
0	4	1	0	3	2	2	2	1	0

1 = { }    5 =  {4, 3, 2, 1 }    2 = {1}    1 = { }    4 = {3, 2, 1}    3 = {2, 1}    4 = {2, 1}

5 = {2, 1}    2 = { 1 }    1 = { }

 

중간 수를 기준으로 왼쪽에 올 수 있는 수와 오른쪽에 올 수 있는 수를 합치면 수열이 완성됩니다.

왼쪽 수와 오른쪽 수를 더하고 기준을 더하면 바이토닉 수열의 길이를 구할 수 있습니다.

왼쪽 수 + 오른쪽 수 + 1이 됩니다.

예를 들어 2번째 값인 5일 때 4 + 1 + 1 = 6의 길이의 바이토닉 수열을 만들 수 있습니다.

 

기준에서 왼쪽에 올 수 있는 수를 저장하기 위해  left[수열의 크기]으로 메모이제이션을 구성하였습니다.

기준에서 오른쪽에 올 수 있는 수를 저장하기 위해  right[수열의 크기]으로 메모이제이션을 구성하였습니다.

 

• 기준값 기준 오른쪽/왼쪽 올 수 있는 수를 저장할 메모이제이션 배열 left,right를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 왼쪽에 올 수 있는 수의 개수를 구하는 함수 leftCal을 만들었습니다.
• 오른쪽에 올 수 있는 수의 개수를 구하는 함수 rightCal을 만들었습니다.
• for문을 통하여 몇 번째 숫자를 최대 숫자로 하는 수열의 길이를 메모이제이션에 저장하였습니다. 
• for문을 통하여 메모이제이션에 저장된 수열의 길이중 Math.max를 사용하여 가장 긴 수열을 얻었습니다.
• System.out.println을 사용하여 가장 긴 수열의 길이를 출력하였습니다.

• left,right에 for문을 통해 올 수 있는 수를 저장하였습니다.
• 위에 알고리즘 설명을 토대로 재귀하도록 leftCal/rightCal함수를 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] left;		//left 메모이제이션
	static int[] right;		//right 메모이제이션
	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];
    	left = new int[index];
    	right = 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++) {
    		leftCal(i);
    		rightCal(index-1-i);
    	}
		//---------최대값 구하기----------
    	for(int i=0;i<index;i++)
    		max = Math.max(max, left[i] + right[i]+1);
    	
    	System.out.println(max);		//결과 출력
    	br.close();
	}
    //------------숫자 기준 왼쪽에 올 수 있는 수 구하는 함수-------------
	public static void leftCal(int depth) {
		int leftResult = 0;
		
		for(int i=depth;i>=0;i--) {
			if(num[depth]>num[i] && leftResult<=left[i])
				leftResult = left[i]+1;
		}
		
		left[depth] = leftResult;
	}
    //------------숫자 기준 오른쪽에 올 수 있는 수 구하는 함수-------------
	public static void rightCal(int depth) {
		int rightResult = 0;
		
		for(int i=depth;i<index;i++) {
			if(num[depth]>num[i] && rightResult<=right[i])
				rightResult = right[i]+1;
		}
		
		right[depth] = rightResult;
	}
}