[Python] 백준/BOJ 24499번: blobyum (Silver 4)

💻 Problem

문제 보러 가기

 

오늘도 블롭은 배고프다. 그래서 블롭은 요리사 연우를 찾아가 맛있는 것을 달라고 부탁했다.

연우는 귀여운 블롭에게 이왕이면 맛있는 음식을 해 주고 싶었기에, 자신이 만드는 데에 가장 뛰어난 애플파이를 만들기로 하였다. 연우는 N개의 애플파이를 만들었으며, 이를 원 모양으로 책상에 배치해 놓았다.

각 애플파이는 하나의 양의 정수로 표현되며, 이는 맛있는 정도를 의미한다. (수가 클수록 더 맛있는 애플파이이다.)

블롭은 N개의 애플파이 중 K개를 먹으려고 한다. 물론 블롭은 힘을 들이지 않고 먹고 싶기 때문에, 연속으로 배치되어 있는 K개의 애플파이를 먹으려 한다.

블롭을 도와서 블롭이 먹을 애플파이의 맛의 합의 최댓값을 구해 주자!

 

✏️ Solution 1

import sys
input = sys.stdin.readline

N, K = map(int, input().split()) # 애플파이의 개수, 먹으려는 애플파이의 개수
A = list(map(int, input().split())) # 애플파이의 맛있는 정도
pie = [0] # 애플파이의 맛있는 정도 누적합
ans = 0 # 먹을 애플파이의 맛의 합의 최댓값

# 누적합 구하기
for i in range(N):
    pie.append(pie[i] + A[i])

# 애플파의 맛의 합의 최댓값 구하기
for i in range(N):
    if i + K <= N:
        total = pie[i + K] - pie[i]
    else:
        total = pie[N] - pie[i] + pie[i + K - N]
    ans = max(ans, total)

print(ans)

최근에 누적합 문제를 풀었어서 자연스럽게 누적합을 떠올려서 풀게 됐다.

i + K > N 일 때, 어떻게 계산해야 할지 좀 머리 아팠다...

직접 대입해 보면서 K가 2일 때, K가 3일 때.. 계산해 보니 pie[N] - pie[i] + pie[i + K - N]이 나왔다.

 

✏️ Solution 2

import sys
input = sys.stdin.readline

N, K = map(int, input().split()) # 애플파이의 개수, 먹으려는 애플파이의 개수
A = list(map(int, input().split())) # 애플파이의 맛있는 정도
A += A # 원형 처리

pie = [0] # 애플파이의 맛있는 정도 누적합
ans = 0 # 먹을 애플파이의 맛의 합의 최댓값

# 누적합 구하기
for i in range(N * 2):
    pie.append(pie[i] + A[i])

# 애플파의 맛의 합의 최댓값 구하기
for i in range(N):
    ans = max(ans, pie[i + K] - pie[i])

print(ans)

아 맞다!!!!!!!! 머리 아프게 계산할 필요 없이 그냥 똑같은 배열 이어 붙이면 원형 처리 됐었지..

전에 무슨 반지 문제에서 이렇게 풀었던 거 같은데 까먹고 있었음 ㅠ;;

뭔가 당한 느낌! 기억해야겠다

 

✏️ Solution 3

import sys
input = sys.stdin.readline

N, K = map(int, input().split()) # 애플파이의 개수, 먹으려는 애플파이의 개수
A = list(map(int, input().split())) # 애플파이의 맛있는 정도
A += A # 원형 처리

current = sum(A[:K])
ans = 0 # 먹을 애플파이의 맛의 합의 최댓값

# 애플파의 맛의 합의 최댓값 구하기
for i in range(K, N + K):
    # 현재 범위의 다음 값 더하고 이전 값 빼기
    current += A[i] - A[i - K]
    ans = max(ans, current)

print(ans)

생각해보니 누적합 구할 필요도 없네..

슬라이딩 윈도우로 푸는 게 더 간단한데...!

최근에 누적합 문제 풀어서 누적합에만 꽂힌 상태로 본 것 같다.

 

시간복잡도는 전부 O(N)이지만 당연히 슬라이딩 윈도우로 푸는 게 조금 더 빠르다