백준(JAVA) 풀이/다이나믹 프로그래밍

백준(JAVA) 11055번 가장 큰 증가 부분 수열 풀이

개발윗미 2022. 4. 20. 15:51

Java으로 구현한 11055번 가장 큰 증가 부분 수열 문제 풀이입니다.

 

https://www.acmicpc.net/problem/11055

 

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

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수

www.acmicpc.net


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] data = new int[n];
		int[] dp = new int[n];
		String[] str = br.readLine().split(" ");
		for (int i=0; i<n; i++) {
			data[i] = Integer.parseInt(str[i]);
			dp[i] = data[i];
		}
		
		int result = 0;
		for (int i=0; i<n; i++) {
			for (int j=0; j<i; j++) {
				if (data[j] < data[i]) {
					dp[i] = Math.max(dp[i], dp[j] + data[i]);
				}
			}
			result = Math.max(result, dp[i]);
		}
		System.out.println(result);
	}
}

 

1. 입력받은 값들을 이루는 dp 배열을 추가로 정의한다.

 

2. 2중 for문을 통해 특정 값을 기준으로 그 이전값까지 값을 비교하고, 이전에서 확인하고 있는 값이 기준값보다 작을 경우

   dp[i] (기준값)와 dp[j] + data[i] (이전값과의 합)을 비교하여 더 큰 값을 dp[i]에 갱신한다.

 

3. 내부 반복문이 종료되면 현재 result 값과 dp[i]의 값을 비교하여 result에 더 큰 값으로 갱신한다.

 

3. 반복문이 모두 종료되면 dp 배열에서 가장 큰 값(result)을 출력한다.