[백준] 21921번 블로그(python)

 

https://www.acmicpc.net/problem/21921

21921번: 블로그

 

1. 난이도 실버 3

 

2. 문제 해결 방법

 

넓이 구간이 고정되어 있으면 슬라이딩 윈도우를 이용하고, 유동적이면 투 포인터를 이용하면 된다.

 

처음에 sum 함수를 while문 속에 넣어서 문제를 풀었는데 O(N^2)가 되어 시간초과가 발생했다.

 

(sum함수의 시간복잡도는 O(N))

 

두 번째로는 투 포인터 방식을 이용했는데, 구간이 유동적이지 않아 굳이 이 방법을 사용할 필요가 없다는 걸 깨달았다.

 

결국 슬라이딩 윈도우 방식으로 수정해 문제를 해결.

 

 

3. SUM함수 이용(시간초과)

n,x = map(int, input().split()) # n = 블로그 운영 x = 기간
visit = list(map(int, input().split()))

start = 0
end = x-1
cnt = 0
visit_max = 0

while end != n:

  if visit_max < sum(visit[start:end+1]): 
    visit_max = sum(visit[start:end+1])
    cnt = 1
  
  elif visit_max == sum(visit[start:end+1]):
    cnt+=1
  
  start+=1
  end+=1

if visit_max == 0:
  print("SAD")
else:
  print(visit_max)
  print(cnt)

 

4. 투 포인터 방식

import sys

input = sys.stdin.readline

n,x = map(int, input().rstrip().split()) # n = 블로그 운영 x = 기간
visit = list(map(int, input().rstrip().split()))

start = 0
end = 0
interval_sum = visit[0]
result = []

while True:

  if end < x-1:
    end+=1
    interval_sum += visit[end]

  else:
    result.append(interval_sum)
    interval_sum -= visit[start]
    end+=1
    interval_sum += visit[end]
    start+=1

  if end == n-1:
    result.append(interval_sum)
    break

if max(result) == 0:
  print("SAD")
else:
  print(max(result))
  print(result.count(max(result)))

 

5. 슬라이딩 윈도우

n,x = map(int, input().split()) # n = 블로그 운영 x = 기간
visit = list(map(int, input().split()))

interval_sum = sum(visit[:x])
visit_max = interval_sum
max_cnt = 1

for i in range(x,n):
  interval_sum+=visit[i]
  interval_sum-=visit[i-x]

  if interval_sum > visit_max:
    visit_max = interval_sum
    max_cnt = 1

  elif interval_sum == visit_max:
    max_cnt+=1

if max(visit) ==0:
  print("SAD")

else:
  print(visit_max)
  print(max_cnt)