1912) Spice it up, up, up, bottom up.

김핌피·2025년 7월 9일

백준 씨스터디

🔗 문제 링크

사용한 알고리즘 : DP

사용한 자료구조: 리스트(배열)

풀이 전략

'연속적으로 선택한 수의 합'이 최댓값이 되는 수들을 찾는다.
여기서 중요한 것은 각 위치의 최적해를 메모리에 저장하여 재사용하는 것이다.
메모이제이션 없는 재귀는 같은 계산을 반복해 비효율적이므로 계산 결과를 저장하는 방식이 필요하다.
점화식을 세울 수 있는 문제의 경우, 완전탐색 등을 사용하는 것보다
DP로 접근하는 것이 훨씬 효율적이라고 들었기 때문에 DP를 채택해보았다.
문제의 답을 구하기 위해서는 현재 위치에서 현재 위치의 수를 포함하는 최대 연속합을 구해야 한다.

점화식: dp[i] = max(arr[i], dp[i-1] + arr[i])

배열을 한 번 순회하며,
계산한 최적해를 dp 배열에 저장한다.

각 위치(i)마다:

이전 위치의 최적해(dp[i-1])를 활용하여
현재 위치의 최적해(dp[i])를 계산한다

내 코드


# 입력
n = int(input())
arr = list(map(int, input().split()))

# DP 배열 생성
dp = [0] * n

# 초기값 설정
dp[0] = arr[0]

# 배열을 한 번 순회하며 최적해 계산
for i in range(1, n):
    # 점화식: dp[i] = max(arr[i], dp[i-1] + arr[i])
    # - arr[i]: 현재부터 새로 시작
    # - dp[i-1] + arr[i]: 이전 최적해에 이어가기
    dp[i] = max(arr[i], dp[i-1] + arr[i])

# dp 배열 중 최댓값 출력
print(max(dp))

다른 사람의 코드

import sys
sys.setrecursionlimit(10**7)

n = int(input())
arr = list(map(int, input().split()))

dp = [-10**15] * n   

def solve(i):
    if i == 0:
        dp[i] = arr[0]
        return dp[i]
    if dp[i] != -10**15: 
        return dp[i]

    # 점화식
    dp[i] = max(arr[i], solve(i-1) + arr[i])
    return dp[i]

print(max(solve(i) for i in range(n)))