BOJ(연속합)(1912)

작성일 | In

연속합 1912

  • 연속된 몇 개의 수를 선택해서,구할 수 있는 가장 큰 값을 구한다.
n = int(input())
arr = list(map(int, input().split()))
# total은 임시적으로 합으로 쓰이며, result는 최종값
total, result = 0, -1000
for i in range(n):
    if arr[i]+total > 0:
        total += arr[i]
        result = max(result, total)
    else:
        result = max(result, total+arr[i])
        total = 0

print(result)

  • 이걸 DP로는 어떻게 풀지?

  • 단순히 이전 수와 비교해서, 더한 값과 더 큰 수 중 큰수를 arr[i]에 집어넣으면 된다.
  • 그리고 그 집어넣은 값과 출력할 result와 비교하여 더 큰 수를 result에 넣는다.
n = int(input())
arr = [0]+list(map(int, input().split()))
result = -1000
for i in range(1, n+1):
    arr[i] = max(arr[i], arr[i] + arr[i-1])
    result = max(result, arr[i])
print(result)

참고자료 codeplus

0%