백준 11053 (가장 긴 증가하는 부분수열) / C++

문제 링크 : www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

> 풀이

 

간단한 동적 계획법 문제입니다. 최근 종만북을 사서 꾸준히 뒤적거리고 있는데, 최근에 본 기억이 나서 바로 풀었네요.

 

저는 down-top 방식의 반복문으로 쌓아가는 방식을 구현이 편하다고 생각하는데, 종만북에서는 top-down 방식을 중심으로 소개하고있어, 종만북 풀이를 토대로 한 코드(top-down)도 같이 올립니다.

 

top-down 방식으로 구현할 경우 A 배열의 start 번째 에서 시작하는 가장 긴 부분수열을 찾는 방식이고, 

 

down-top 방식으로 구현할 경우 A 배열의 n번째 까지의 가장 긴 부분수열을 찾는 방식입니다.

 

말로 풀어쓰려니 조금 애매하네요 ㅋㅋ

 

 

<top-down>

#include <bits/stdc++.h>
using namespace std;

int dp[1001];
int A[1001];
int N;

int memo(int start) {
        int& ret = dp[start];
        if (ret != 0) return ret;

        ret = 1;
        for (int next = start + 1; next < N; next++)
                if (A[start] < A[next])
                        ret = max(ret, memo(next) + 1);
        return ret;
}

int main(void) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) scanf("%d", &A[i]);

        int res = 0;
        for (int i = 0; i < N; i++)
                res = max(res, memo(i));

        printf("%d", res);
        return 0;
}

<down-top>

#include <bits/stdc++.h>
using namespace std;

int dp[1001];
int A[1001];
int N;

int main(void) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
                scanf("%d", &A[i]);
                dp[i] = 1;
        }

        for (int i = 1; i < N; i++) {
                int res = 1;
                for (int j = 0; j < i; j++) {
                        if (A[i] > A[j])
                                res = max(res, dp[j] + 1); 
                }
                dp[i] = res;
        }
        
        sort(dp, dp + N);
        printf("%d", dp[N - 1]);
        return 0;
}