[백준 알고리즘] (DP) 11722번 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, 1105

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

 

백준 알고리즘 11722번

 

 

<첫 번째 오답 풀이>

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

원래대로는 arr[5](배열이 1부터 시작한다고 가정)인 29에서 dp[5]는 4가 되어야 맞으나,

i=5, j=3에서 4로 업데이트 되었다가, 직후에 j++과 함께 i=5, j=4인 상황에서

dp[5]=dp[4]+1, 즉 3으로 업데이트가 되어버린다.

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

 

역시나 dp[5]에서 3이 저장되어 있는 모습 확인.

이런 문제는 문제가 된 23라인 부등호 방향만 다시 바꿔주면 금방 해결된다.

 

<정답 풀이>

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