[BOJ] 11722. 가장 긴 감소하는 부분 수열(DP, LDS)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

LIS문제(최소 증가 부분 수열)의 반대 개념의 LDS(최소 감소 부분 수열) 문제이다.

LIS 알고리즘에서 조건만 살짝 바꿔주면 되는 생각보다 간단한(?)문제다. ㅋ_ㅋ

#. Code

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

#include <cstdio> #include <algorithm> using namespace std;   int A[1001], DP[1001];   int main(void) {     int n, i, j, res = 0;     //freopen("input.txt", "rt", stdin);     scanf("%d", &n);     for (i = 1; i <= n; i++) {         scanf("%d", &A[i]);           int tmp = 0;         for (j = 1; j < i; j++) {             if (A[i] < A[j] && tmp < DP[j])                 tmp = DP[j];         }           DP[i] = tmp + 1;         if (DP[i] > res)             res = DP[i];     }       printf("%d\n", res);       return 0; } Colored by Color Scripter

cs

line 17) 이 line에서 A[i] 와 A[j]를 비교하는 등호만 바꾸어주면 된다.