가장 긴 증가하는 부분 수열
BOJ 11053 가장 긴 증가하는 부분 수열
boj 11053 가장 긴 증가하는 부분 수열 D[i]가 어떻게 작동해야 문제에서 원하는 답을 잘 찾아낼 수 있을까를 생각해봤다. 위 그림과 같이 작동해야하는데, 그래서 D[i]를 i번째 원소를 마지막으로 하는 가장 긴 부분 수열의 길이라고 정의하였다. a[i]는 수열을 담는 배열이다. D[i]는 길이이기에 1씩 점점 증가하는 방식으로 식을 정의해줘야하는데, 언제 1씩 증가시켜야하는지 조건을 정해주는 것이 이 문제의 핵심이다. 먼저 코드를 보고 코드에 대해 설명해보겠다. #include #include using namespace std; int n; int mx; int a[1005]; int D[1005]; int main(void) { ios_base::sync_with_stdio(0); cin.t..