[백준] 12014번 주식 (C++)

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

 

 

이 문제는 N일과 주식을 사야하는 K일이 존재한다.

이후 N일만큼 그날의 주가가 주어졌을때 일수가 지남에 따라 주식이 증가하는 날을 부분적으로 선택하여 K일 이상으로 살 수 있는경우 1을 출력 못할 경우 0을 출력하는 문제이다.

 

문제를보면 굉장히 비슷한 문제들을 풀었던 기억이 떠오를 것이다 https://www.acmicpc.net/problem/11053 과 비슷하다고 생각할 수 있을 것이다.

 

따라서 dp를 사용하여 그 중 최댓값을 기록하여 그 최댓값이 K보다 작은지 이상인지 비교하여 출력해주었다.

 

이때 배열의 최대 길이는 1만이다 결국 부분수열의 시간복잡도는 O(N^2)이며 시간제한은 5초이기 때문에 통과할 수 있다고 생각하였다.

 하지만 T의 최대 크기가 100이기 때문에 불가능하지만 제출해보니 통과가 되었다....

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

// int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
// int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int dx[] = {1, 1, 1};
int dy[] = {-1, 0, 1};
int T, N, M;
int arr[10001];
int dp[10001];
int cnt = 1;

void solve() {
    int tmp = 1;
    fill(dp, dp + N+1, 1);

    for(int i = 1; i < N; i++) {
        for(int j = 0; j < i; j++) {
            if(arr[i] > arr[j]) {
                dp[i] = max(dp[j]+1, dp[i]);
            }
            tmp = max(dp[i], tmp);
        }
    }

    if(tmp >= M) {
        cout << 1 << endl;
    }
    else cout << 0 << endl;
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N >> M;

        cout << "Case #" << cnt << endl;

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

        solve();
        cnt++;
    }
}

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

    input();
}

 

solve 함수를 살펴보면

void solve() {
    int tmp = 1;
    fill(dp, dp + N+1, 1);

    for(int i = 1; i < N; i++) {
        for(int j = 0; j < i; j++) {
            if(arr[i] > arr[j]) {
                dp[i] = max(dp[j]+1, dp[i]);
            }
            tmp = max(dp[i], tmp);
        }
    }

    if(tmp >= M) {
        cout << 1 << endl;
    }
    else cout << 0 << endl;
}

 

입력받은 배열과 dp 배열이 존재한다 첫번째로 dp배열을 1씩 다 초기화 해주었다. 그 이유는 증가하는 부분수열 특성상 자기 자신을 선택하는 경우는 모든 경우에서 다 가능하기 때문에 1로 초기화 한 이후

배열을 순차적으로 순회할때 현재 지점 이전을 끝까지 순회하며 선택한 지점보다 큰 경우는 증가할 수 있기 때문에 가능한 최댓값으로 update하였다.

 

이후 최대 일수와 K를 비교하여 1 또는 0을 출력해주었다.