시간복잡도를 줄이는 기술 3. 전처리 - 숫자들의 합이 7의 배수

문제

N개의 서로 다른 숫자가 차례대로 주어집니다. 이들 중 연속하게 고른 숫자들의 합이 7의 배수가 되게 그룹으로 묶으려 합니다. 이렇게 만든 그룹 중 최대 크기를 구하는 프로그램을 작성해보세요.

아이디어

기록하는 새로운 배열을 만들어 해결하는 것이 포인트

1. 합 배열을 구한다.(Prefix_sum)
2. 맨 뒤 (모든 수의 합)에서 부터(for i range(N,0,-1) - 맨 앞의 수( for j in range(0,i)를 을 빼가며 7의 배수인지 체크한다.
3. 만약 7의 배수가 있다면, for j 를 탈출한다. (앞에서 부터 돌기 때문에, 가장 큰 그룹이다. 뒤에는 돌 필요 X)

 

코드

N=int(input())
arr= [0]

# 합 배열을 구한다. 
# 맨 뒤에서 부터 
for _ in range(N):
    arr+=list(map(int,input().split()))

prefix_sum = [0]*(N+1)

for i in range(1,N+1):
    prefix_sum[i]=prefix_sum[i-1]+arr[i]

ans=0
for i in range(N,0,-1):
    for j in range(i):

        if (prefix_sum[i]-prefix_sum[j])%7==0:
            ans=max(ans,i-j)
            break #없을 시, 시간 초과 (모든 n을 다 탐색할 필요 없음)
        

print(ans)

 

새로운 접근

1. 기록하는 배열에 합을 더하지 않고, 누적합 값의 7로 나눈 나머지 값을 배열에 저장한다.
2. 나머지가 같은 위치 두 곳을 양끝으로 하는 구간을 잡게되면, 구간 내 수들의 합이 7의 배수가 된다.

import sys

MOD = 7
INT_MAX = sys.maxsize
INT_MIN = -sys.maxsize

# 변수 선언 및 입력:
n = int(input())
a = [0] + [
    int(input())
    for _ in range(n)
]

# 전처리로 모든 시작부터의 누적합에 대해
# 0 ~ 6 나머지가 되는 최소와 최대 idx를 구해 저장해둘 배열을 선언합니다.
max_idx = [INT_MIN] * MOD
min_idx = [INT_MAX] * MOD

# 나머지가 0일 때에는 앞에 아무 숫자도 없을 때가 최소입니다.
min_idx[0] = max_idx[0] = 0

sum_div7 = 0
for i in range(1, n + 1):
    # 1부터 i번째까지 원소를 더한 값의
    # 7로 나눈 나머지를 sum_div7에 저장합니다.
    sum_div7 += a[i]
    sum_div7 %= 7

    # 7로 나눈 나머지 값들 중
    # 등장 위치의 최솟값과 최댓값을 갱신해줍니다.
    max_idx[sum_div7] = max(max_idx[sum_div7], i)
    min_idx[sum_div7] = min(min_idx[sum_div7], i)
 
ans = 0
for i in range(MOD):
    # 나머지가 i인 누적합의 최대 index에서 최소 index를 빼주면
    # 앞에 나온 숫자들의 합이 7로 나눈 나머지가 i일때의
    # 숫자들의 합이 7의 배수가 되는 최대 구간을 알 수 있습니다.
    ans = max(ans, max_idx[i] - min_idx[i])

# 정답을 출력합니다.
print(ans)