Swea_3307

SWEA 3307번

Link: 3307번: 최장 증가 부분 수열

---

문제 설명

완전탐색 문제인줄 알고 앞에서 썼던 DFS 써서 풀었다가 시간초과났던 문제.

조합을 하는건 맞는데, DP로 풀었어야 풀리는 문제였다.

최근에 DP 공부를 하고있었는데도 DP로 풀어야겠다는 생각은 여전히 들지 않았다.

어찌어찌 테스트케이스는 맞출수 있도록 구현했는데, 제출해보니 한개도 못맞히더라.

시험장가서 테스트케이스 맞히고도 탈락하는 경우가 왕왕 있다던데, 이런 경우인가 싶었다.

덤으로 이딴 실력으로 시험장에 가지 않았다는 점이 천만다행.

풀이에 대해 설명하자면, 우선 입력받은 숫자들 중 수열의 시작점을 for문을 통해 정한다.

그 다음, 남은 숫자들을 택해서 증가수열을 만들고 그 증가수열의 길이를 갱신하며 최대값을 구하는 문제다.

이를 위한 조건으로 2가지를 넣었다.

첫째는 다음 숫자가 반드시 수열의 시작점보다 큰 숫자일 것.

두번째는 증가수열의 길이가 증가하는 방향일 것.

이 두가지를 만족하지 못하면 증가수열에 숫자를 포함하지 않고, 다음 숫자들을 계속 살펴보는 식이다.

이 문제도 답보고 겨우 풀었는데, DP 문제에 대한 감을 살짝 잡은 것 같다.(아직 확실하진 않음)

이런 최대값 찾는 DP문제의 경우 조건에 맞아 DP 배열의 값을 갱신한 후, 최대값을 갱신하는 작업을 반복하는 방식인 것 같다.

너무 당연한 말을 한것 같지만, 이런 감 찾는데 정말 오래걸렸다.

아무튼

될때까지 하자.

---

정답 코드

//
// Created by Keith_Lee on 08/01/2019.
//

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int T;

int main(){
    cin >> T;

    for(int test=1; test<=T; test++){
        int maximum = 0;
        int N;

        cin >> N;

        int numbers[N];
        int DP[N];

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

        bzero(DP, sizeof(DP));

        for(int i=0; i<N; i++){
            for(int j=i+1; j<N; j++){
                if(numbers[j] < numbers[i]) continue;
                if(DP[j] >= DP[i] + 1) continue;
                DP[j] = DP[i] + 1; // 증가수열이면서 수열 count가 증가한다면 1 더해줌.
                maximum = max(maximum, DP[j]); // 최대값 갱신.
            }
        }

        cout << '#' << test << ' ' << maximum+1 << '\n';
    }
}

---