[백준 알고리즘] (DP) 11055번 Java풀이

 

 

만약 이 문제 전에 11053번 문제를 안풀어봤다면 먼저 풀어보고 오기를 추천한다.

https://www.acmicpc.net/problem/11053

 

 

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

알고리즘 문제풀이(PS) 시작하기

 

백준 알고리즘 11055번

 

<첫 번째 오답 풀이>

package dp;
 
import java.util.Scanner;
 
public class N11055 {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n+1];
        int dp[] = new int[n+1];
        int sum[] = new int[n+1];
        
        for(int i=1; i<=n; i++) {
            arr[i] = sc.nextInt();
        }
        sc.close();
        for(int i=1; i<=n; i++) {
            dp[i] = 1;
        }
        for(int i=1; i<=n; i++) {
            sum[i] = arr[i];
        }
        
        for(int i=2; i<=n; i++) {
            for(int j=1; j<i; j++) {
                if(arr[j]<arr[i] && dp[i]<=dp[j]) {
                    dp[i] = dp[j]+1;
                }
                if(dp[i]>dp[j] && arr[i]>arr[j]) {
                    sum[i] = sum[j]+arr[i];
                    
                }
            }
        }
        
        int max =0;
        for(int i=1; i<=n; i++) {
            max = Math.max(max, sum[i]);
        }
        System.out.println(max);
    }
 
}