[백준][C++/Python] 1912번: 연속합 (253)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

1912번: 연속합

 

생각의 흐름

일단 처음에 보고 딱 DP를 생각하지는 않았다. 다만 input값이 100000 까지라는 점이 매우 거슬렸다.

나또한 맨처음에는 2중 for문 도는 방법이 생각났지만, 그러면 100000,00000 O(n^2) 까지라는 소리인데, 이건 백퍼 시간초과 날것이 눈에 훤하게 보였다.

​

O(n^2) 알고리즘은 n이 최대 10,000 근처일 때까지 유효하다고 기억하고 있었다.

​

그럼 뭐 다른방법 있겠는가? 그냥 DP가 그다음으로 떠오른 방법이다.

​

DP[i] 를 i번째 index까지의 배열의 연속합중 최대값 이라고 의미를 부여하였다.

그럼 index가 증가할때마다 DP[i] 값과 DP[i-1] + Arr[i] 값을 비교하여 더 큰값을 DP[i]에 대입하면 되는 문제였다.

​

이는 i-1번째 까지의 최대합, 즉 DP[i-1]을 알고있는 상황에서 i번째 원소를 더한것이 큰지, 아니면 그냥 i번째 원소자체만으로 새롭게 연속합을 시작하는 것이 더 큰지를 비교하는 것 이다.

​

예를 들어 -1 10 이 있다고 해보자.

dp[1]은 -1이며, dp[2]는 10이 된다. dp[2]를 구할때 10에 -1을 더한값 보다는, 그냥 10을 넘겨주는것이 더 크기때문이다.

 

나의 코드

1) C++

#include <bits/stdc++.h>
using namespace std;

int arr[100001];
int dp[100001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int num;
	cin >> num;

	for(int i = 1; i <= num; i++) cin >> arr[i];
	
	dp[1] = arr[1];
	for(int i = 2; i <= num; i++){
		dp[i] = (arr[i] > arr[i] + dp[i-1]) ? arr[i] : arr[i] + dp[i-1];
	}
	
	int res(0);
	for(int i = 1; i <= num; i++){
		res = max(res, dp[i]);
	}
	
	cout << res;
	
	return 0;
}

 

2) Python

import sys

N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
DP = [0 for _ in range(N)]

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

print(max(DP))