1~100개 사이의 증가하는 수열이 주어지는데 여기서 몇개를 지우려고 한다. 그런데 조건이 있다.
연속적으로 지워야 하고 반드시 복구가 가능해야 한다.
예를들어 2 3 4 5 6 10 이런 배열이 있다면 3,4,5를 지울 수 있다는 이야기이다.
지운 결과가 2 _ _ _ 6 10 이렇게 남아있다면 손쉽게 3,4,5를 바로 복구할 수 있다.
배열이 주어졌을 때 가장 많이 원소를 지웠을 때 몇개를 지웠는지 출력해야 한다.
a[0] = 0, a[++n] = 1001로 두고 차가 1인 증가수열의 최대 길이를 구하면 된다.
#include <iostream> #include <algorithm> using namespace std; int n, a[103]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; a[0] = 0; for (int i = 1; i <= n; ++i) cin >> a[i]; a[++n] = 1001; int cnt = 1, ans = 0; for (int i = 1; i <= n; ++i) { if (a[i] == a[i - 1] + 1) cnt++; else cnt = 1; ans = max(ans, cnt); } cout << max(ans - 2, 0); return 0; } | cs |
'codeforces > #520 div2' 카테고리의 다른 글
| D. Fun with Integers (0) | 2018.11.17 |
|---|---|
| C. Banh-mi (0) | 2018.11.17 |
| B. Math (0) | 2018.11.17 |