처음에 ans = max(ans ... 부분을 for문을 안 돌리고 idx = 0 에서 시작하면 가장 큰 경우를 구할 수 있을 줄 알았다.
하지만 idx > 0 에서 시작해서 더 큰 값을 구하는 경우가 존재한다.
ex
8 1 2 3 4 5 6 7 8 9
idx = 0 부터하면 2
idx = 1 부터하면 9
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
#include <stack>
using namespace std;
int stb[10001]; // single table
int scache[100001]; // single cache
int tb[1001][1001];
int cache[1001][1001];
int n;
int go(int idx) {
if (scache[idx] != -1) {
return scache[idx];
}
int& ret = scache[idx] = 1;
for (int i = idx+1; i < n; ++i) {
if (stb[idx] < stb[i]) {
ret = max(ret,go(i) + 1);
}
}
return ret;
}
int main(void) {
memset(scache, -1, sizeof(scache));
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> stb[i];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, go(i));
}
cout << ans;
return 0;
}
'알고리즘' 카테고리의 다른 글
| [EAZY] 백준 15624 피보나치 7 (0) | 2018.04.02 |
|---|---|
| [DP] 백준 11051 이항계수2 (0) | 2018.04.02 |
| [EASY] 백준 2167 2차원 배열의 합 (0) | 2018.04.02 |
| [DP] 백준 14916 거스름돈 (0) | 2018.04.02 |
| [DP] 백준 9084 동전 (0) | 2018.04.02 |