BOJ(백준) 2559[수열]

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 2559번을 풀어보겠습니다. 이 문제는 주어진 온도 리스트에서 연속된 K일 동안의 온도의 합이 최대가 되는 값을 찾는 문제입니다.

 

문제 URL: https://www.acmicpc.net/problem/2559

 

1. 문제 설명

주어진 온도 리스트에서 연속된 K일 동안의 온도의 합이 최대가 되는 값을 찾는 문제입니다. 주어진 온도 리스트에서 연속된 K일 동안의 온도의 합이 최대가 되는 값을 계산해야 합니다.

 

2. 접근법

1. 각 테스트 케이스마다 온도 리스트가 주어집니다.

2. 연속된 K일 동안의 온도의 합을 계산하여 최대값을 찾습니다.

3. 누적합(prefix sum)을 이용하여 효율적으로 계산합니다:

• 온도 리스트의 누적합을 계산합니다.

• 누적합을 이용하여 K일간의 합을 구하고, 그 중 최대값을 찾습니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 첫 번째 줄에서 N과 K를 입력받음
N, K = map(int, input().split())
# 측정한 온도를 리스트로 입력받음
arr = list(map(int, input().split()))
# 누적합을 담을 리스트 선언, 길이는 N+1로 설정
prefix = [0] * (N + 1)

# 누적합 계산
for i in range(N):
    prefix[i + 1] = prefix[i] + arr[i]

# 최대 합을 찾기 위한 리스트 선언
ans = []
# K일간의 합을 구해서 리스트에 추가
for i in range(K, len(prefix)):
    ans.append(prefix[i] - prefix[i - K])

# 최대 합 출력
print(max(ans))

 

4. 코드 설명

1. 입력 처리

• 첫 번째 줄에서 N과 K를 입력받습니다.

• 두 번째 줄에서 N개의 온도를 입력받아 리스트로 저장합니다.

2. 누적합(prefix sum) 계산

• 온도 리스트의 누적합을 계산하여 prefix 리스트에 저장합니다.

• prefix[i]는 arr 리스트의 0번부터 i-1번까지의 원소의 합을 나타냅니다.

3. K일간의 합 계산

• prefix 리스트를 이용하여 연속된 K일간의 합을 구합니다.

• prefix[i] - prefix[i - K]는 i-K부터 i-1까지의 원소의 합을 나타냅니다.

4. 최대 합 계산

• K일간의 합 중 최대값을 찾아 출력합니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_03_01_2559.py at main · pcy4196/coTest