[BOJ] 1912. 연속합

Python3,DP

문제

입출력

입출력 예시

나의 풀이

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

dp = [0 for i in range(n)]

for i in range(n):
    for j in range(i-1, i):
        dp[i] = max(dp[i], dp[j]+a[i])
    
if sum(dp) == 0:
    print(max(a))
else:
    print(dp)

연속된 숫자의 합이므로 반복문을 i-1로 한정했다.
현재 값과 이전값을 더한 값 중에 더 큰 값을 dp 배열 안에 넣는다.

만약 -1, -2, -3, -4, -5 처럼 더할 수록 값이 커지지 않는 경우는 따로 처리를 해줘야 한다. (문제 조건에서 반드시 하나 이상을 선택해야 한다고 했으므로)
그래서 dp 배열에 합이 0이면(아무것도 들어오지 않았다면) 수열 a중 가장 큰 값 하나를 출력한다.

다른 사람 코드

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

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

dp 배열 없이 바로 입력 받은 a 수열에 넣었다.

1부터 n-1까지 반복문을 돌고 현재값과 이전값+현재값 중 큰 값을 수열 a에 넣는다.
그리고 수열a에서 가장 큰 값을 출력한다.

피드백

처음부터 끝까지 혼자 힘으로 풀어낸 문제이다. 하지만 효율성적인 측면에서는 더 발전할 필요가 있어 다른 사람 코드를 봤는데, 수열 a로 하니 훨씬 코드가 간결해졌다.

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

dp = [0 for _ in range(n)]
dp[0] = a[0]

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

흠 .. 근데 이건 왜 안 될까