백준 [14931] 물수제비(Python3)

문제 링크 : https://www.acmicpc.net/problem/14931

14931번: 물수제비 (SUJEBI)

 

완전 탐색

1 ~ 1,000,000 까지 순회하면서 간격을 1, 2, 3, ..., L을 두어 탐색했을 때
탐색한 값의 합이 가장 큰 걸 구한다.

간격별로 탐색 횟수를 나열해보면 아래와 같다.

- 간격이 1일 땐, 1,000,000번 탐색.
- 간격이 2일 땐, 500,000번 탐색.
- 간격이 3일 땐, 333,333번 탐색.
- 간격이 4일 떈, 250,000번 탐색.

...

-간격이 1,000,000일 땐, 1번 탐색.

이렇게 간격이 커질 수록 탐색 범위는 점점 줄어들게 되고
간격이 500,000을 넘으면 1번씩만 탐색한다.
총 탐색 횟수를 계산하면 최대 탐색 범위 2억번(제한 시간 2초)을 넘지 않으므로,
O(NlogN)의 시간 복잡도로 문제를 해결할 수 있다.

 

코드

L = int(input())
scores = list(map(int, input().split()))

ans, ansI = 0, 0
for i in range(0, L):
    total = 0
    index = i + 1
    for j in range(i, L, index):
        total += scores[j]
    if total > ans:
        ans = total
        ansI = index
print(ansI, ans)