백준 1912 연속합 파이썬

백준 1912 연속합 풀이

접근방식

1. 연속해서 최대값을 구해야 하기 때문에 max 함수 활용하기
2. 바로 이전 숫자와 자기 자신을 더했을 때 그 중 큰 값을 고르기
3. for문을 수행하면 자연스럽게 최댓값만을 가지는 리스트를 갖게됩니다.

시간 초과 코드

처음에는 2중 for문을 이용해서 [0:0], [0:1], [0:2] 등
i번째부터 리스트 끝 원소까지 합 중 가장 큰 값을 저장하려 했습니다.
하지만 결과적으로 시간 초과 오류를 범했고,
단일 for문만을 이용해서 더 효율적으로 풀 수 있었습니다.

import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

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

ans = -int(1e9)

for i in range(n):
    for j in range(i+1, n):
        ans = max(ans,sum(arr[i:j]))

print(ans)

정답 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

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

for i in range(1, n):
    arr[i] = max(arr[i], arr[i-1] + arr[i])

print(max(arr))

해당 문제는 실버 2 난이도의 다이나믹 프로그래밍 문제였습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady