[백준] 11055. 가장 큰 증가하는 부분 수열
2024. 1. 9. 11:09ㆍCS/Algorism
https://www.acmicpc.net/problem/11055
dp 문제이고 내가 실수한 코드는 다음과 같다.
for (int i = 1; i < n; i++) {
for (int j = i - 1; j >= 0; j--) {
if (input[j] < input[i]) {
dp[i] = dp[j] + input[i];
break;
}
}
}
그런데 만약 input 값이 "20 60 50 70"인 경우 반례가 된다.
내가 작성한 코드대로 계산하면, i가 3일 때 dp[3] = dp[2] + input[3] 으로 dp[3]이 140이 된다.
그러나 답은 dp[1] + dp[input] 으로 150이다.
따라서 input[i]의 값보다 작은 input[j]를 찾았으면 다 된 것이 아니라 최댓값이 더 있을 수 있으므로, 다음과 같이 i보다 작은 인덱스를 모두 살펴봐야 한다.
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (input[j] < input[i]) {
dp[i] = Math.max(dp[i], dp[j] + input[i]);
}
}
}
전체 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// 시간복잡도: O(N^2) = 100,000
public class Main {
static int n;
static int[] input;
static long[] dp;
static long answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
input = new int[n];
dp = new long[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
input[i] = Integer.parseInt(st.nextToken());
dp[i] = input[i];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (input[j] < input[i]) {
dp[i] = Math.max(dp[i], dp[j] + input[i]);
}
}
}
for (long i : dp) {
answer = Math.max(answer, i);
}
System.out.println(answer);
}
}
이 문제와 유사한 문제: https://www.acmicpc.net/problem/11053
'CS > Algorism' 카테고리의 다른 글
[백준] 1912. 연속합 (0) | 2024.01.12 |
---|---|
[백준] 15486. 퇴사 2 (0) | 2024.01.12 |
[백준] 5427. 불 (1) | 2024.01.06 |
[백준] 12100. 2048 (Easy) (0) | 2024.01.02 |
[백준] 1697. 숨바꼭질 (0) | 2023.12.29 |