[백준] 가장 긴 감소하는 부분 수열 (11722번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

[백준] 가장 긴 감소하는 부분 수열 (11722번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

---

[접근 방법]

 

<11053번 : 가장 긴 증가하는 부분 수열>을 아주 조금 비튼 문제이다.

https://notorious.tistory.com/180

[백준] 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA) / 400 - 다이나믹 프로그래밍 1

가장 긴 감소하는 부분 수열을 구하는 문제이다.

 

DP를 갱신하는 조건 문을 바꾸기만 하면 된다.

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 수열 A의 크기 N (1 ≤ N ≤ 1,000)
        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N+1];
        int[] DP = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<N+1; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }       

        for(int i=1; i<=N; i++){
            DP[i] = 1;

            for(int j=1; j<i; j++){

                if(A[j] > A[i] && DP[i] < DP[j] + 1){
                    DP[i] = DP[j] + 1;
                }
            }
        }

        // 가장 긴 감소하는 부분 수열 길이 구하기

        int min = -1; 
        // Math.max() 활용
        for(int i=1; i<=N; i++){
            min = Math.max(DP[i], min);
        }


        bw.write(min + "\n");
        bw.flush();
        bw.close();
    }
}

---

삼항 연산자(ternary operator)

삼항 연산자는 자바에서 유일하게 피연산자를 세 개나 가지는 조건 연산자입니다.

 

삼항 연산자의 문법은 다음과 같습니다.

문법

조건식 ? 반환값1 : 반환값2

 

물음표(?) 앞의 조건식에 따라 결괏값이 참(true)이면 반환값1을 반환하고, 결괏값이 거짓(false)이면 반환값2를 반환합니다.

[출처] http://www.tcpschool.com/java/java_operator_etc

코딩교육 티씨피스쿨

 

삼항 연산자를 활용한 "가장 긴 감소하는 부분 수열의 길이" 갱신 과정

// 삼항 연산자 활용
int min = -1; 
for(int i=1; i<=N; i++){
	min = DP[i] > min ? DP[i] : min;
}