21921 : 블로그

• 실버 3

시간제한	메모리제한	정답비율
1초	512MB	40.744%

input : 시작한지 n일,x일 / 1~n일차 방문자수 split output : x일 동안 들어온 최대 방문자수 출력. 0 = “SAD” / 기간

x일동안 최고라는 것은 x길이만큼 덩어리의 방문자수가 제일 큰 것을 말하는 것으로 보임. 그니깐 다 잘라서 해야하는지? 근데 250000인데 완전탐색으로 하면 안될 것으로 보이고, 그리디로 해야할듯. 근데 완전탐색이 제일 맞는 것으로 보이는데

시간초과

누적합을 사용하지 않으면 시간초과가 계속났다. O(n*x)의 시간복잡도를 가지고 있는 것을 누적합을 사용하면 O(n)의 시간복잡도로 축소시킬 수 있다. 기존의 식은 x일씩의 하위 배열 sum을 계산하므로 반복계산으로 시간이 많이 소요된다. 예상한대로 n의 범주가 큼으로 최적화가 필요했다. sum을 사용하지 않으면서 단순 덧뺄셈으로 구간합을 구할 수 있게 변경했어야 했다.

python

import sys, os

problem_num = "21921"

path = os.getcwd() + f"\\txt\\{problem_num}" + ".txt"
sys.stdin = open(path, "r")
input = sys.stdin.readline

def find_max_visit(n, x, visitors):
    if max(visitors) == 0:
        print("SAD")
    else:
        cumulative_sum = [0] * (n + 1)

        for i in range(n):
            cumulative_sum[i + 1] = cumulative_sum[i] + visitors[i]

        max_visit = 0
        hash_table = {}

        for i in range(n - x + 1):
            subarray_sum = cumulative_sum[i + x] - cumulative_sum[i]

            if subarray_sum > max_visit:
                max_visit = subarray_sum
                hash_table[subarray_sum] = 1

            elif subarray_sum == max_visit:
                hash_table[subarray_sum] += 1

        print(max_visit)
        print(hash_table[max_visit])


n, x = map(int, input().split())
visitors = list(map(int, input().split()))
find_max_visit(n, x, visitors)

SAD