20.06.17 개발일지 - 가장 긴 증가하는 부분

여러 테스트케이스를 추출해보고 값을 비교해 보았으나, 틀린 점을 발견하지 못했습니다.

물론 제출 시 계속 통과도 하지 못했습니다.

그래서 다른 사람의 답안을 보고 다시 작성하였습니다.

 

#include <iostream>
#include <array>
#include <algorithm>

using namespace std;

int main()
{
    int N = 0, temp = 0;
    array<int, 1000> Series;
    array<int, 1000> Sublength;
    Series.fill(-1);
    Sublength.fill(1);

    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> temp;
        Series[i] = temp;
    }

    int sol = 1;
    for (int i = 0; i < N; ++i)
    {
        Sublength[i] = 1;
        for (int j = 0; j < i; ++j)
        {
            if (Series[i] > Series[j])
            {
                Sublength[i] = (Sublength[i] > Sublength[j] + 1) ? Sublength[i] : (Sublength[j] + 1);
            }
        }
        sol = (sol > Sublength[i]) ? sol : Sublength[i];
    }

    cout << sol << endl;

    return 0;
}

자신보다 앞의 있는 숫자가 자신보다 작을 경우,

그 숫자의 sublength + 1과 자신의 현재 sublength중 큰 수를 저장합니다.

그리고 현재의 solution과 비교하여 solution보다 클 경우, 그 값을 solution으로 저장합니다.

 

정석적인 DP 풀이인데, 이걸 보니까 제가 짰던 것이 DP가 아니라 Greedy Algorithm이었던 것 같습니다.

그 와중에 예외를 찾지 못했다는 점이 한탄스러울 뿐입니다.