반응형
문제 출처 :
알고리즘 분석 :
문제 해결에 필요한 사항
1. 구현
2. Dynamic Programming
아래 주석에 더 자세히 달아두었다.
구현과 dp를 이용하면 쉽게 해결 할 수 있다.
소스 코드 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | #include <iostream> typedef long long ll; ll arr[100004]; ll dp[100004]; int main() { freopen("input.txt", "r", stdin); int tCase; scanf("%d", &tCase); for (int tc = 1; tc <= tCase; tc++) { int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < n + 2; i++) arr[i] = dp[i] = 0; for (int i = 0; i < n; i++) scanf("%lld", &arr[i]); int youSa = -1; int s = 0; int ans = 0; for (int e = 0; e < n; e++) { /* 유사증가수열 포인트가 없으면서 arr[e-1] > arr[e]일때 10 20 30 40 50 3 일때 3은 유사증가수열 포인트 */ if (youSa == -1 && arr[e - 1] > arr[e]) youSa = e; /* 유사증가수열 포인트가 있으면서 arr[e-1] > arr[e]일때 10 20 30 1 20 30 2 일때 s를 이전 포인트(1)로 보내고 유사증가수열 포인트를 2로 갱신 */ else if (youSa != -1 && arr[e - 1] > arr[e]) { s = youSa; youSa = e; } /* 유사증가수열 포인트가 있으면서 arr[e-1] <= arr[e]이고 arr[e-2] > arr[e]일때 10 20 30 2 40 3 50일때 s는 2로 보냄 */ else if (youSa != -1 && arr[e - 1] <= arr[e] && arr[e - 2] > arr[e]) s = youSa; int l = e - s + 1; if (l - k + 1 > 0) dp[e] = (l - k + 1); } for (int i = 0; i < n; i++) ans += dp[i]; printf("#%d %lld\n", tc, ans); } return 0; } | cs |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[2098번] 외판원 순회 (0) | 2019.03.10 |
---|---|
[268-C번] Beautiful Sets of Points (0) | 2019.03.09 |
[16646번] 콘서트 (0) | 2019.03.07 |
[16953번] A → B (0) | 2019.03.05 |
[16956번] 늑대와 양 (0) | 2019.03.03 |