합이 7이 되는 부분수열(Subsequences Summing to Sevens)

농부 존(Farmer John)의 소 N마리가 일렬로 서 있습니다. 존은 소들을 구별하기 위해 각 소에게 고유한 정수 ID를 부여했습니다.

존은 연속된 소 그룹의 사진을 찍고 싶어 합니다. 하지만 어릴 적 1부터 6까지의 숫자와 관련된 트라우마가 있어서, 연속된 소들의 ID 합이 정확히 7의 배수가 되는 그룹의 사진만 찍으려고 합니다.

존이 사진을 찍을 수 있는 가장 큰 연속된 소 그룹의 크기(마리 수)를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 소의 마리 수 N이 주어진다. (1 ≤ N ≤ 50,000)

다음 N개의 줄에 걸쳐 각 소의 정수 ID가 한 줄에 하나씩 차례대로 주어진다. (각 ID는 0 이상 1,000,000 이하의 정수이다.)

출력

ID의 합이 7의 배수가 되는 가장 큰 연속된 소 그룹의 크기를 출력한다. 만약 조건을 만족하는 그룹이 단 하나도 존재하지 않는다면 0을 출력한다.

(참고: 많은 수의 ID를 합칠 경우 표준 32비트 정수형의 범위를 벗어날 수 있습니다. C/C++을 사용할 경우 "long long"과 같은 64비트 정수 자료형을 사용하는 것을 권장합니다.)

힌트

예제에서 두 번째 소부터 여섯 번째 소까지의 구간을 선택하면 ID의 합이 5 + 1 + 6 + 2 + 14 = 28이 되며, 이는 7의 배수입니다.

이 그룹의 크기는 5이며, 이보다 더 큰 조건을 만족하는 그룹은 없습니다.

출처

USACO 2016 January Contest, Silver

Line 1: \(N\) (\(1 \le N \le 50000\)). Next \(N\) lines: an ID each (\(0 \le \text{ID} \le 10^6\)).

Print the length of the longest valid contiguous group.

riseoj 작성

출처 Online Judge > GoldOJ