728x90
문제
접근 방식
수열 {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이 주어졌을 때 1, 100, 2, 60, 50 처럼
들쑥날쑥한 부분 수열이 아닌 1, 2, 50, 60 처럼 증가하는 부분 수열 중에서
합이 가장 큰 부분 수열을 구해야 하는 문제다.
우선 간단하게 생각해보면 이전 수보다 큰 값이 나올 때까지 모두 합해주면
특정 수로 끝나는 부분 수열의 합을 구할 수는 있다.
1로 끝나는 부분 수열은 {1} = 1
1 > 100 > 2 (이전 수인 100보다 작음)
== 100으로 끝나는 부분 수열은 {1, 100} = 101
2 > 50 > 60 > 3 (이전 수인 60보다 작음)
== 60으로 끝나는 부분 수열은 {2, 50, 60} = 112
위와 같이 특정 수로 끝나는 부분 수열의 값을 알 수 있지만
문제에서 요구하는 부분 수열과는 조금 다르다.
문제에서는 {1, 2, 50, 60} = 113 처럼 연속된 부분 수열이 아니라도
값이 증가하기만 한다면 부분 수열로 만들 수 있기 때문에
{1, 2, 50, 60} 과 같은 수열을 만들기 위해서는
{1}과 {2, 50, 60}을 합치면 된다는 것을 알 수 있다.
즉, 60으로 끝나는 부분 수열의 합은
60보다 작은 부분 수열의 합들을 더한 값이 된다.
풀이
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[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int max = arr[0];
int[] dp = new int[n];
dp[0] = arr[0];
for (int i = 1; i < n; i++) {
dp[i] = arr[i];
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = Math.max(dp[j] + arr[i], dp[i]);
}
}
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
}
'Java > Algorithms' 카테고리의 다른 글
| [백준] 14501번 : 퇴사 (1) | 2023.12.24 |
|---|---|
| [백준] 9461번 : 파도반 수열 (1) | 2023.12.23 |
| [백준] 2193번 : 이친수 (0) | 2023.12.20 |
| [백준] 12852번 : 1로 만들기 2 (0) | 2023.12.18 |
| [백준] 11659번 : 구간 합 구하기 4 (0) | 2023.12.18 |
