https://www.acmicpc.net/problem/11055
11055번: 가장 큰 증가 부분 수열
수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
import java.util.Scanner;
public class Main {
public static int n;
public static int[] arr;
public static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
arr = new int[n + 2];
dp = new int[n + 2];
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
}
dp[1] = arr[1];
for (int i = 2; i <= n; i++) {
dp[i] = arr[i];
int maxDp = 0;
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j]) {
maxDp = Math.max(maxDp, dp[j]);
dp[i] = maxDp + arr[i];
}
}
}
int max = dp[1];
for (int i = 1; i <= n; i++) {
if (dp[i] > max) {
max = dp[i];
}
}
System.out.println(max);
}
}
|
cs |
11053번 문제와 매우 유사한 문제이다
https://we1cometomeanings.tistory.com/86
[java 백준] 실버 2/11053번 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20,..
we1cometomeanings.tistory.com
문제를 풀면서 놓친 부분
1. dp[i]=dp[j]+arr[i]
|
1
2
3
4
5
6
7
8
9
10
11
|
dp[1] = arr[1];
for (int i = 2; i <= n; i++) {
dp[i] = arr[i];
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] += arr[j];
}
}
}
|
cs |
7번째 줄 처럼 dp[i]+=arr[j]라고 점화식을 짜버리면
100 110 90 80 70 80 90 1 2 3 일때,
dp[7]=70+80+90=240 이여야 하는데, arr[4]인 80도 arr[7]인 90보다 작기 때문에 80+70+80+90=320이 되버린다. 그렇기 때문에 240이 나오기 위해서는
if(arr[i]>arr[j]){
dp[i]=dp[j]+arr[i]
}
2. 최대값
하지만
dp[i]=dp[j]+arr[i] 이렇게만 써버리면 2,1,5,6,7일때, 예외가 발생한다.
예를 들어 dp[3]을 구한다고 해보자. 그러면 i는 3일 것이고 j를 1부터 2까지 돌려보겠다.
i=3이고, j는 1일 때 --> 2<5 이므로 if 조건을 만족시킨다. dp[3]=dp[1]+arr[3]을 하면 dp[3]=7이다.
i=3이고 j=2일때 1<5이므로 if 안에 조건을 만족시킨다. dp[3]=dp[2]+arr[3] 을 하면 dp[2]=1 (arr[2]가 arr[1]보다 작으므로 dp[2]=arr[2]가 된다) 에 5를 더하면 6이 된다.
이렇게 되면 j가 1일때 (7)가 j가 2일 때(6) 보다 크지만 j가 2일때가 1보다 늦게 나오기 때문에 dp[3] 값을 덮어쓰므로 결론적으로 dp[3]=6이된다.
그래서 2,1,5,6,7 일 때 답은 20이여야하지만 dp[i]=dp[j]+arr[i] --> 얘를 써버리면 답은 19가 된다.
그러면 감이 올거다 바로 max를 쓰면된다 j가 1일때랑 j가 2일 때 중 더 큰 값을 골라서 걔를 dp[i]에 더해주면 된다.
for (int i = 2; i <= n; i++) {
dp[i] = arr[i];
int maxDp = 0;
for (int j = 1; j < i; j++) {
if (arr[i] > arr[j]) {
maxDp = Math.max(maxDp, dp[j]);
dp[i] = maxDp + arr[i];
}
}
}
반레를 알아보고 싶을 때
https://squareyun.tistory.com/18
[Java] 백준 11055 : 가장 큰 증가 부분 수열
문제 링크 1. 1시간 소요. 점화식 세우는 아이디어는 금방 떠올라서 코드를 쭉쭉 써내려 갔다. 그러나 오답처리가 되어 질문 검색을 통해 반례를 찾아서 수정하는 데에 오랜 시간이 걸렸다. 점화
squareyun.tistory.com
https://geehye.github.io/baekjoon-11055/#
DynamicProgramming 백준 알고리즘 자바 11055 ‘가장 큰 증가 부분 수열’ 문제풀이
Problem수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분
geehye.github.io
'알고리즘 > DP' 카테고리의 다른 글
| [DP기초] 필요한 동전의 최소개수 구하기 (0) | 2021.08.06 |
|---|---|
| [DP기초] 계단오르기 (0) | 2021.08.06 |
| [java 백준] 실버 2/1912번 연속합 (0) | 2021.08.05 |
| [java 백준] 실버 3/ 2579번 계단오르기 (0) | 2021.08.05 |
| [java 백준] 실버 2/11722번 가장 긴 감소하는 부분 수열 (0) | 2021.08.04 |
댓글