티스토리 뷰

문제: 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 != -&& 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)11974 Subsequences Summing to Sevens  (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
댓글
댓글쓰기 폼