[백준/JAVA] 11055번: 가장 큰 증가하는 부분 수열

🔺 문제

11055번: 가장 큰 증가하는 부분 수열

 

 

🔺 코드

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);
    }
}
 

✅ 해결 아이디어
✔ 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 구현)

[백준 11055] 가장 큰 증가 부분 수열 (자바)