심화된 DP문제들을 풀어보려고 한다.
https://www.acmicpc.net/workbook/view/7836

이 중에서 골드까지의 문제를 풀며 심화된 DP들을 배워본다.
DP는 점화식을 구하지 못하면 절대 못푸는 문제라고 생각하기에,
오랫동안 구하지 못하면 바로 답을 본다.

1. 11722 - DP

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

해결

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int A[N+1] = {0, };
    for(int i=1;i<=N;i++)
    {
        cin >> A[i];
    }

    int dp[N+1] = {0, };
    int lastNum[N+1] = {0, };

    dp[1] = 1;
    for(int i=1;i<=N;i++)
    {
        dp[i] = 1;
        for(int j=i-1; j>=0; j--)
        {
            if(A[i] < A[j] && dp[i]<=dp[j])
            {
                dp[i] = dp[j] + 1;  // dp의 최대값 갱신
            }
        }
    }
    int max = 0;
    for (int i = 1; i <= N; i++)
    {
        if(max < dp[i])
        {
            max = dp[i];
        }
    }
    
    cout << max;

    return 0;   
}

풀이

i번째 원소는 본인 이전의 원소들을 순회하며,
본인보다 값이 더 큰게 있다면,
그리고 본인의 dp값보다 더 큰게 있다면,
dp의 값을 해당 dp값으로 변경하며 계속 순회한다.

그렇게 최대값을 갱신할 수 있게 된다.

2. 15486 - DP

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

시도

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int t[N + 1] = {
        0,
    };
    int p[N + 1] = {
        0,
    };

    int d[N + 1] = {
        0,
    };
    for (int i = 1; i <= N; i++)
    {
        cin >> t[i];
        cin >> p[i];
    }

    d[1] = p[1];
    for (int i = 2; i <= N; i++)
    {   
        // 마지막 날을 초과하는 상담은 제외
        if(i+t[i] > N+1)
        {
            continue;
        }

        int time = 0;
        int max = p[i]; // 현재비용을 max로 둔다.
        for (int j = i - 1; j >= 1; j--)
        {
            time++;
            if(time == t[j])      // 현재 노드를 진행하기 전의 노드를 구한다.
            {
                max = d[j] + p[i];//가장 큰 값만 구한다.
            }
        }
        d[i] = max;     //max가 갱신되지 않으면 그냥 현재비용.
    }

    // 출력
    int answer=0;
    for(int i=1;i<=N;i++)
    {
        if(answer < d[i])
        {
            answer = d[i];
        }
    }

    cout << answer;
    return 0;
}

모든 예제도 맞았고, 다른 반례들도 맞을거라고 생각한다.
하지만 시간초과가 났다.

흠..
2중 for문 부분이 문제라고 생각하는데..
2중 for문 없이 어떻게 이전 노드를 구할지 떠오르지 않는다.

음..

for문을 현재 1부터 N까지 진행하는데,
해당 인덱스 이전의 값들을 또 다시 비교하므로
왔다-다시뒤로 갔다
이런 형태가 된다.

그래서.. 혹시모르니
for문을 그냥 N부터 1까지 역순으로 취하도록 수정해본다.

시도 2

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int t[N + 1] = {
        0,
    };
    int p[N + 1] = {
        0,
    };

    int d[N + 1] = {
        0,
    };
    for (int i = 1; i <= N; i++)
    {
        cin >> t[i];
        cin >> p[i];
    }

    d[1] = p[1];
    d[N] = p[N];

    // N부터 시작하여 본인 이전의 d들을 갱신하는 알고리즘
    for (int i = N; i >= 2; i--)
    {   
        d[i] = max(d[i], p[i]);
        // 마지막 날을 초과하는 상담은 제외
        if(i+t[i] > N+1)
        {
            d[i] = 0;   // 시간이 안되면 아예 할 수 조차 없으므로 0으로 만듦
            continue;
        }

        int time = 0;
        for (int j = i - 1; j >= 1; j--)
        {
            time++;
            if(time == t[j])    // 자신 이전에 할 수 있는 일이 있다.
            {
                // 그러면 그 날의 값은 현재 d랑 비교했을 때, max값
                d[j] = max(d[j], p[j] + d[i]);
            }
        }
        //max가 갱신되지 않으면 그냥 현재비용.

        //cout << "Day : " << i << "\n";
    }

    // 출력
    int answer=0;
    for(int i=1;i<=N;i++)
    {
        if(answer < d[i])
        {
            answer = d[i];
        }
    }

    cout << answer;
    return 0;
}

안된다.
역시 시간초과.

본인 이전의 날을 계산하기 위해선, 해당 노드로부터
for문을 무조건 돌려야만 한다고 생각한다.

그런데 왜?

시도 3

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    // 초기화 및 선언
    int t[N + 1] = {
        0,
    };
    int p[N + 1] = {
        0,
    };
    int d[N + 1] = {
        0,
    };

    // 입력값
    for (int i = 1; i <= N; i++)
    {
        cin >> t[i];
        cin >> p[i];
    }

    // 핵심
    for (int i = N; i >= 1; i--)
    {   
        if(i+t[i] > N+1)    // 시간 상 할 수 없는 일이라면,
        {
            d[i] = d[i+1];  // 다음날의 일을 하도록 함.
        }
        else
        {
            d[i] = max(d[i+1], p[i] + d[i+t[i]]);   
            // 다음날의 일과, 다음시간의 일을 더한 값 중 큰 값을 현재 값으로 둠.
        }
    }

    cout << d[1];
    return 0;
}

질문게시판에 된다고 올린 알고리즘을 그대로 사용해보았다.
틀렸다고 뜬다..
왜??

반례도 다 되는데 왜..

배열 선언부를 main밖으로 빼니까 된다.. 왜??
왜?

하.. 도저히 모르겠다.. 질문게시판에 글을 하나 남겼다.

https://www.acmicpc.net/board/view/125145#post

지역변수로 N을 크기로 하는 VLA라는 변수기반크기 배열을 선언하면,
백준 컴파일러가 오류를 잡아내기 힘든데,
스택영역의 메모리를 벗어난 오류가 발생했음에도,
VLA이기에 그냥 틀렸다는 결과를 냈다는 것 같다.