-
[백준] 21921번 블로그(python)Python/BAEKJOON 2023. 1. 2. 23:23728x90
문제)
알고리즘)
- 시간복잡도를 생각하지 않고 문제를 본다면 대부분 for문과 sum 함수를 반복해서 사용해서 코드를 짜면 될 것 같지만
예시)
for i in range(N-X+1): #윈도우의 크기와 graph의 크기를 고려해서 움직일 수 있는 횟수만큼 반복
now = sum(graph[i:i+X]) #매번 sum함수로 해당 윈도우안에 해당하는 값 sum이 경우 시간복잡도에서 걸리게 되어 시간초과가 됩니다.(for문과 sum 동시에 반복시 n^2의 시간복잡도 갖는다 최악!!)
- 핵심은 이름 그대로 Sliding Window처럼 지나가면서 윈도우에서 벗어나는 값은 빼고 새로 들어오는 값 더하기
start += graph[i] #들어오는 값 start -= graph[i-X]빠져나가는 값
코드)
#블로그 import sys input = sys.stdin.readline N, X = map(int, input().split()) #총일 윈도우 크기 graph = list(map(int, input().split())) #일별 방문자 수 리스트 if max(graph) == 0:# 전체가 0이여야 나오는 경우가 "SAD" print("SAD") else: start = sum(graph[:X])#맨 처음 초기값만 sum함수 사용 total = start cnt = 1 #최대합이 갯수는 0이 아닌 경우 모두 1 for i in range(X, N): start += graph[i] start -= graph[i-X] if start > total: total = start cnt = 1 elif start == total: cnt += 1 print(total) print(cnt)
728x90'Python > BAEKJOON' 카테고리의 다른 글
[백준] 24090번 알고리즘 수업 - 퀵 정렬 1(python) (0) 2023.07.02 [백준] 2667번 단지번호붙이기(python) (0) 2022.06.22 [백준] 11047번 동전 0(python) (0) 2022.03.26 [백준] 1057번 토너먼트(python) (0) 2022.03.26 [백준] 2579번 계단오르기(python) (0) 2022.03.26