[백준알고리즘] 1912번: 연속합 -Python

[백준알고리즘] 1912번: 연속합 -Python

https://www.acmicpc.net/problem/1912

1912번: 연속합

2019-08-20

첫 번째 풀이

 

이번 문제는 LCS에서처럼 뻘짓을 하지 않아서 좀 빨리 풀렸다!!ㅎㅎ

주어진 수열에서 연속하는 부분 수열들 중 최대 합을 구하면 된다.

이번에는 단순히 max만 비교해서 유지했기 때문에 풀면서 딱히 배열을 사용하지 않았다.

 

풀면서 max_val이라는 전체에서 여태까지 구한 최대합을 나타내는 변수와 tmax라는 max_val을 구하기 위해서 직접 리스트의 값들을 더해가면서 나타내는 변수를 사용했다. tmax에서는 배열의 값을 하나씩 읽어와서 그 값을 더해나간다. 하지만 현재까지 tmax가 음수였는데, 더해야 할 수가 양수일 경우에는 에 양수를 더한 값보다 그 양수 자체가 더 크기 때문에 양수로 바꿔주었다. max_val은 계속해서 tmax와 비교했기 때문에 최대였던 값을 기억하고 있게 된다.

 

이제 보니 뻘짓 안 한 것보다 문제가 쉬웠던 것 같다.

 

 

아래는 코드이다.

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
max_val = arr[0]
tmax = arr[0]

for t in arr[1:]:
    if tmax < 0 and t > 0:
        tmax = t
    else:
        tmax += t
    
    max_val = max(max_val, tmax, t)
    # print("t : {} == tmax : {} max_val : {}".format(t, tmax, max_val))

print(max_val)

2020-02-12

두 번째 풀이

새로 문제를 풀어봤는데 같은 얘기이기는 하나 변수 값들을 여러 개 두지 않아서 더 쉬워 보였다.

 

우선 N+1개의 리스트에 입력값을 1번 인덱스부터 인덱싱할 수 있도록 해준다. 그리고 누적 값은 범위 밖인 -1001을 초기값으로 잡아주고 max 값을 구하기 위해서 반복해준다.

 

accumulate에 들어갈 수 있는 값은 accumulate[i] = max(accumulate[i-1] + arr[i], arr[i])로, 이전까지의 누적 값에 현재 값을 더한 값과 현재 값을 비교해서 더 큰 값을 넣어주도록 했다.

 

import sys

N = int(sys.stdin.readline())
arr = [0]
arr += list(map(int, sys.stdin.readline().split()))

accumulate = [-1001]
for i in range(1, N + 1):
    accumulate.append(max(accumulate[i-1] + arr[i], arr[i]))

sys.stdout.write(str(max(accumulate)))

 

2020-04-08

두 번째 풀이

내용은 크게 차이가 없다.

n = int(input())
dp = list(map(int, input().split()))
for i in range(1, n):
    dp[i] = max(dp[i], dp[i-1]+dp[i])
print(max(dp))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다