[백준] S2 11055번 가장 큰 증가 부분 수열 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

11055번: 가장 큰 증가 부분 수열

[문제] 

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

[입력]

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

[출력]

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

 

 

---

[풀이]

1. dp배열(누적합을 담아둘 배열)을 만들어준다.

2. 이전에 자신 보다 작은 값이 왔다면 해당 값의 경우에 자신을 더한 값들을 비교하며 가장 큰 것으로 채운다.

3. 마지막에 모든 dp 배열을 돌면서 가장 큰 값을 구한다.

[접근]

1. 문제를 보자마자 자신의 값을 이전 값들과 비교해서, 누적된 최고값에 자신을 더하면 된다고 생각했다.

2. dp[0]은 항상 자기 자신의 값이 들어온다.

3. 이후 dp[1] ~ dp[n - 1]까지는 이전의 값들과 비교를 해서 값이 현재의 값보다 작으면서 누적 합이 가장 큰 것을 찾아 해당 값에 현재의 값을 더한 것을 입력해준다.

4. 모든 dp 배열을 채워주고, 그 중 가장 큰 값을 구한다.

[코드]

package BOJ_silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_S2_11055_김재욱 {
	static int n; // n
	static int dp[]; // dp 배열
	static int sequence[]; // 입력받은 수열을 담을 배열
	static int result; // 결과
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		// 초기화
		dp = new int[n];
		sequence = new int[n];
		result = Integer.MIN_VALUE;
        
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 수열 입력받기
		for(int i = 0; i < n; i++) {
			sequence[i] = Integer.parseInt(st.nextToken());
		}
		
		// 시작은 항상 자기 자신
		dp[0] = sequence[0];
		
		// 수열 끝까지 탐색
		for(int i = 1; i < n; i++) {
			dp[i] = sequence[i];
			// 앞에 숫자보다 자신이 작은 경우가 나올수 있으니 항상 자기자신을 먼저 담아두고 생각
			
			for(int j = 0; j < i; j++) {
				if(sequence[i] > sequence[j]) { // 현재 값이 이전 값보다 크면
					// 값을 넣어줘야한다.
					// 어떤 값? > 자기 자신 + 이전에 자신보다 작은 경우 중 가장 큰 값
					dp[i] = Math.max(dp[j] + sequence[i], dp[i]);
				}
			}
		}
		
		// 결과를 얻는 과정
		for(int i = 0; i < n; i++) {
			if(dp[i] > result) {
				result = dp[i];
			}
		}
		
		System.out.println(result);
	}
}