코테/백준
[백준/JAVA] 11055번: 가장 큰 증가하는 부분 수열
imname1am
2023. 7. 20. 00:27
반응형
🔺 문제
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
|
import java.util.*;
import java.io.*;
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[] cost = new int[N];
int[] dp = new int[N]; // LIS 배열
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0 ; i < N ; i++) {
cost[i] = Integer.parseInt(st.nextToken());
}
// dp[i] : '부분'증가수열에서 'i번째 항'이 '최댓값'인 부분증가수열의 누적합
dp[0] = cost[0];
int result = dp[0];
for(int i = 1 ; i < N ; i++) {
dp[i] = cost[i]; // 일단 자신의 값을 dp에 저장
for(int j = 0 ; j < i ; j++) {
if(cost[i] > cost[j]) { // 기준값이 더 큰 경우
dp[i] = Math.max(dp[i], dp[j] + cost[i]); // dp배열에 저장되는 값 : 부분 수열의 합
}
}
result = Math.max(result, dp[i]);
}
System.out.println(result);
}
}
|
cs |
✅ 해결 아이디어
✔ DP - LIS
- dp 배열에 저장되는 값 : 부분 수열의 합. (부분 수열 길이 x)
- dp[i] : '부분'증가수열에서 'i번째 항'이 '최댓값'인 부분증가수열의 누적합
💥 유의사항
• Line 19-20 : dp[0] = cost[0] 선언하고, 그 다음에 result = dp[0]으로 해야 함!! 둘이 순서 바뀌면 result에 초기값이 0 들어가면서 98퍼에서 틀림.....
💬 느낀 점
오호... LIS 감을 잡다..
사실 19-20번째 줄 순서 바꿔서 제출했었는데 계속 틀렸었다....
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 230802 | 240309 |
(참고)
[백준,BOJ 11055] 가장 큰 증가 부분 수열( JAVA 구현)
-내 생각 이 문제는 이전에 풀었던 가장 긴 증가 부분 수열인 LIS 문제와 동일한 문제였다. 차이점이라 한다면, DP 배열에 저장되는 값이 부분 수열의 길이가 아닌, 부분 수열의 합이 된다는 점이
fbtmdwhd33.tistory.com
[백준 11055] 가장 큰 증가 부분 수열 (자바)
백준 11055번 가장 큰 증가 부분 수열 (자바) 출처 www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그
hidelookit.tistory.com
반응형