평범한 개발 일지

본 문제는 그냥 보자마자 번뜩 아이디어가 떠올랐다. 문제
내 생각은 현재를 기준으로 전의 값들을 비교하면 된다고 생각이 들었다. 즉, 다이나믹 프로그래밍 문제이다.
즉, 현재 값 > 전의 값 & 지금까지의 길이 < 전의 값까지의 길이 이다.
처음에는 이 문제가 가장 큰 증가하는 부분 수열인줄 알고 그렇게 풀었다가 거기서 변수만 조금 수정하면 되서 그렇게 성공했다. 다이나믹 프로그래밍같은 문제는 차근차근 생각하고 어떤 변수를 저장하고 사용할지를 생각하면 될 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define SIZE 1001
using namespace std;

int n;
int dp[2][SIZE] = { 0 };

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

void solve() {
    dp[1][1] = 1;
    for (int i = 2; i <= n; i++) {
        int num = dp[0][i];
        for (int j = 1; j < i; j++) {
            if (dp[0][j] < num && dp[1][j] > dp[1][i] ) {
                dp[1][i] = dp[1][j];
            }
        }
        dp[1][i]++;
    }

}

void print() {
    int max = dp[1][1];
    for (int i = 2; i <= n; i++)
        if (dp[1][i] > max)
            max = dp[1][i];
    printf("%d", max);
}

int main(void) {
    input();
    solve();
    print();
}