https://www.acmicpc.net/problem/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)
[코드]
import java.util.*;
public class BaekJoon_11055 {
static int n;
static int[] a,dp;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
a=new int[n];
dp=new int[n]; // 각 원소의 가장 큰 증가 부분 수열의 합
for(int i=0;i<n;i++)
a[i]=sc.nextInt();
for(int i=0;i<n;i++) {
dp[i]=a[i]; // 수열의 시작은 자기 자신이기 때문에 자기 자신의 값으로 초기화
// 자신보다 왼쪽에 있는 값 탐색
for(int j=0;j<i;j++) {
// 자신보다 값이 작다면 dp값 갱신
if(a[i]>a[j])
/*
* 자신의 증가 부분 수열의 합과
* 원소 j의 증가 부분 수열의 합에 자기 자신의 배열 값을 더한 값 중
* 큰 값으로 갱신한다.
*/
dp[i]=Math.max(dp[i],dp[j]+a[i]);
}
}
// 수열의 합이 가장 큰 값 찾기
int max=-1;
for(int i=0;i<n;i++)
max=Math.max(max, dp[i]);
System.out.println(max);
}
}
[고찰]
이번 문제는 예전에 풀었던 백준 11053번 가장 긴 증가하는 부분수열 문제와 구하는 값만 다른 똑같은 문제였다. 11053번은 수열의 길이를 구하는 반면에 이번 문제는 수열의 합을 구하는 문제였다. 2중 for문을 사용하여 모든 원소를 탐색하는 방법으로 해결하는 것이 더 간단했다.
2중 for문을 사용하여 현재 배열의 인덱스보다 배열 인덱스들을 탐색하는데, 이때 현재 배열(i) 값 보다 작은 배열(j) 값을 찾았으면 현재의 증가하는 부분 수열의 합 or j 번째 까지의 증가하는 부분 수열의 합 + i번째 배열 값 중 큰 값으로 dp를 갱신하면 된다.
'백준' 카테고리의 다른 글
[백준_17413] 단어 뒤집기 2 (0) | 2021.09.18 |
---|---|
[백준_16918번] 봄버맨 (0) | 2021.09.18 |
[백준_1174번] 줄어드는 숫자 (0) | 2021.09.18 |
[백준_2003번] 수들의 합 2 (0) | 2021.09.17 |
[백준_2435번] 기상청 인턴 신현수 (0) | 2021.09.17 |