문제: icpc.me/11974
N마리의 소가 각각의 고유 ID를 가지고 있을 때 연속된 소의 고유 ID의 합이 7의 배수인 구간의 길이를 출력하는 문제이다.
소를 입력 받은 후에 소의 partial sum을 저장한 뒤 partial sum을 7로 나눈 나머지를 저장한다면
해당 값이 같은 가장 긴 구간이 답이될 것이다.
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 | #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; ll n, a[50000], p[50000], r; int main() { scanf("%lld", &n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); for (int i = 0; i < n; i++) { if (!i) p[i] = a[i]; else p[i] = p[i - 1] + a[i]; } for (int i = 0; i < n; i++) p[i] = p[i] % 7; for (ll i = 0; i < 7; i++) { ll x = -1; ll y = n + 1; for (ll j = 0; j < n; j++) { if (p[j] == i) { x = max(j, x); y = min(j, y); } } if (x != -1 && y != n + 1) { r = max(r, x - y); } } printf("%lld", r); return 0; } | cs |
'알고리즘 관련 > BOJ' 카테고리의 다른 글
BOJ)13325 이진 트리 (1) | 2017.01.18 |
---|---|
BOJ)11975 Build Gates (0) | 2017.01.18 |
BOJ)11973 Angry Cows (0) | 2017.01.18 |
BOJ)10216 Count Circle Groups (0) | 2017.01.17 |
BOJ)13913 숨바꼭질4 (0) | 2017.01.17 |