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

문제 링크

11057번: 오르막 수

---

주의사항

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

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

---

문제 설명

---

접근 방법

다이나믹 프로그램

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

 

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

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

 

이 문제에 핵심은

1. 증가하는 수열 중 가장 큰 수열의 합을 결과로 출력해야 합니다.

 

배열

 

DP : 메모이제이션 배열

 

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

 

DP[]와 sequence 배열을 이용하여 가장 큰 증가하는 수열의 합을 구하였습니다.

 

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

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

1(1)	2(100)	3(2)	4(50)	5(60)	6(3)	7(5)	8(6)	9(7)	10(8)
1	101	3	53	113	6	11	17	24	32

 

DP[3]을 확인해보면

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

 

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

 

DP[5]을 확인해보면

DP[1~4]에서 60보다 작은 수열 값에서 가장 큰 DP값은 DP[4]입니다.

 

DP[4] + sequence[5] = 53 + 60 = 113

 

DP[7]을 확인해보면

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

 

DP[6] + sequence[7] = 6 + 5 = 11

 

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

 

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

 

문제에 해결알고리즘은

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

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

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

 

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

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

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int A;
	static int[] sequence, DP;	//수열 저장 배열, 메모이제이션 배열
    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
        //---------입력값 저장 및 배열 초기화--------
    	A = Integer.parseInt(br.readLine());
    	sequence = new int[A];
    	DP =  new int[A];
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<A;i++)
    		sequence[i] = Integer.parseInt(st.nextToken());
    	
    	DP[0] = sequence[0];	//DP 초기화
    	int result = cal();		//DP 구성 후 최대값 주는 함수 실행
    	bw.write(result + "\n");	//최대값 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //규칙을 통해 DP을 구성 후 최대값 출력하는 함수
    static int cal() {
    	int max = DP[0];
    	for(int i=1;i<A;i++) {
    		int cur = Integer.MIN_VALUE;
    		for(int j=i-1;j>=0;j--) {
    			if(sequence[i] > sequence[j])	//더 큰 DP값 존재시
    				cur = Math.max(cur, DP[j]);
    		}
    		if(cur==Integer.MIN_VALUE)	//해당 이하의 DP값 존재 안할 때
    			DP[i] = sequence[i];
    		else
    			DP[i] = cur + sequence[i];
    		max = Math.max(max, DP[i]);
    	}
    	return max;		//최대값 반환
    }
}