[코딩테스트] 백준(BAEKJOON) - 가장 큰 증가 부분 수열(Java, 11055번)

안녕하세요~

오늘도 코딩테스트 문제 같이 풀어보겠습니다~

 

오늘 풀어볼 문제는 비교적 쉬웠던 LIS를 활용한 문제입니다.

거두절미하고 문제부터 만나보겠습니다.

 

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

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

 

기존의 LIS 와 다른점은 길이를 구하는게 아닌 저장해놓은 array들의 합을 더하며 최대값을 찾는데 있습니다.

제가 작성한 코드입니다.

 

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


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {

			BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
			int count=Integer.parseInt(bf.readLine());
			
			int[] arr=new int[count+1];
			int[] dp=new int[count+1];
			
			String line=bf.readLine();
			String[] lineSplit=line.split(" ");
			
			for(int i=1;i<=count;i++)
				arr[i]=Integer.parseInt(lineSplit[i-1]);
			
			for(int i=1;i<=count;i++)
			{
				dp[i]=arr[i];
				for(int j=1;j<=i;j++)
				{
					if(arr[j]<arr[i])
						dp[i]=Math.max(dp[i], dp[j]+arr[i]);
				}
				
				
			}
			
			int max=-1;
			
			for(int i=1;i<=count;i++)
				max=Math.max(max, dp[i]);
			
			System.out.println(max);
			
	}

}

기본 로직은 같되 dp에서 +1을하며 길이를 구하는게 아닌 arr[i]값을 더하며 요소의 합을 구하는 부분이 다릅니다.

간단하게 마무리하겠습니다.

 

감사합니다. :D