[백준] 1912, 13398: 연속합 1, 2 (Python)

1912: 연속합

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

1912번: 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

dp[n]에 n번째 원소까지 고려한 경우의 최대 연속합을 저장한다. 이때 점화식은 dp[n] = max(dp[n-1]+arr[n], arr[n]) 이다. 즉 직전까지의 연속합(dp[n-1])이 양수인 경우에는 n번째 원소(arr[n])까지 더한 값이 최댓값이 되고 직전까지의 연속합이 음수인 경우에는 n번째 원소만 있는 경우가 최댓값이 된다. 반드시 숫자를 하나 이상 선택해야 하므로 dp[0] = arr[0]으로 초기화하고 for문을 돌렸다. 

# 1912: 400 - 다이나믹 프로그래밍 1 - 연속합
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n # arr[i]까지 고려했을 때 최대 연속합
dp[0] = arr[0]
for i in range(1, n):
    dp[i] = max(arr[i], dp[i-1]+arr[i]) # arr[i] 혹은 이전 최대 연속합+arr[i]
print(max(dp))

---

13398: 연속합 2

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

13398번: 연속합 2

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

이전 문제와 다른 점은 수열에서 수를 하나 제거할 수 있다는 점이다. 그러므로 수를 하나도 제거하지 않은 기존의 경우와 수열의 어떤 한 원소를 제거한 경우 두 가지를 고려해야 한다.

나는 처음에 수열에서 가장 작은 수를 제거한 경우가 최댓값을 만드는 경우라고 생각했으나 수열의 원소가 모두 양수인 경우에는 수를 하나도 제거하지 않는 경우에 최댓값을 가지므로 이 가정은 틀렸다.

그 다음에는 dp를 이차원 리스트로 만들어 dp[0]에는 0번째 원소를 제거한 경우의 최댓값, dp[1]에는 1번째 원소를 제거한 경우의 최댓값, ..., dp[n]에는 아무 원소도 제거하지 않은 경우의 최댓값을 저장하려고 했다. 즉 크기가 (n+1)*(n+1)인 리스트를 이용해 답을 구하려고 했으나 이 경우 당연하게도 메모리 초과가 떴다.

 

그래서 다른 코드를 참고해보니 대부분 수를 하나도 제거하지 않은 경우를 담은 배열 하나, 수를 하나 제거한 경우를 담은 배열 하나 총 2개의 배열을 이용해 풀었다. dp를 2*n 리스트로 만들어 해결했고, 수를 하나도 제거하지 않은 배열 dp[0]은 이전 문제와 동일한 점화식으로, 원소 하나를 제거한 dp[1]은 새로운 점화식으로 풀었다.

원소 하나를 제거한 경우는 다음의 두 가지 경우를 고려하여 풀었다. 

1) i번째 원소 이전에 이미 원소 하나를 제거한 경우 - i번째 원소를 더함 (dp[1][i] = dp[1][i-1] + arr[i])

이전에 원소를 제거한 경우이므로 dp[1][i-1]을 사용한다.

arr[i] 단독의 경우는 dp[0] 배열에서 고려하므로 dp[1]의 첫번째 경우에서 추가적으로 고려하지 않는다. 

2) i번째 원소를 제거하는 경우 - i번째 원소를 더하지 않음 (dp[1][i] = dp[0][i-1])

이전에 원소를 제거하지 않은 경우이므로 dp[0][i-1]을 사용한다. 

dp[1][0]의 경우 0번째 원소 이전의 원소를 제거하는 경우는 있을 수 없으므로 0번째 원소를 제거하는 경우가 되며 dp[1][0] = 0이 된다. 배열 생성 시 모든 원소를 0으로 초기화했으므로 따로 초기화해주지 않아도 된다. 

 

최종적으로는 dp의 최댓값을 출력하면 되는데, 이때 주의해야 할 점이 두 가지가 있다.

1) print(max(dp[0]), max(dp[1]))로 출력하면 dp[1][0]의 0이 출력되어 잘못된 결과가 나올 수 있다. 모든 원소가 음수인 경우에는 최댓값도 음수가 나오는데 초기화용 0이 음수보다 크기 때문에 발생하는 문제이다. 따라서 일반적으로는 arr[0] 또는 -1e9로 초기화한 변수 answer를 실시간으로 dp[0][i], dp[1][i]와 비교하여 최댓값을 저장하는 식으로 푼다. (-1e9는 무한대에 가까운 음수이므로 입력되는 수열의 원소가 무조건 더 큰 값을 갖게 된다)

2) 배열을 0으로 초기화했으므로 N이 1인 경우 입력된 값이 음수면 초기화용으로 사용한 0이 출력되어 오답으로 판정된다. 따라서 N이 1인 경우에는 바로 arr[0]을 출력해줘야 한다. answer를 arr[0]으로 초기화한 경우에는 신경쓰지 않아도 된다. 

 

* 배열 생성 시 arr[0]으로 초기화하면 dp[0][0]을 따로 초기화하거나 N이 1인 경우를 처리해주지 않아도 되지만 dp[1][0]을 0으로 초기화해줘야 하는 점을 놓치면 안된다. 

# 13398: 401 - 다이나믹 프로그래밍 1 연습 - 연속합 2
n = int(input())
arr = list(map(int, input().split()))
dp = [[0] * n for i in range(2)] # dp[1][0] = 0 
dp[0][0] = arr[0]
answer = arr[0]
for i in range(1, n):
    dp[0][i] = max(dp[0][i-1] + arr[i], arr[i])
    dp[1][i] = max(dp[1][i-1] + arr[i], dp[0][i-1])
    answer = max(answer, dp[0][i], dp[1][i])
print(answer)