백준 1912 연속합 (C++)

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

1912번: 연속합

 

문제!

---

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

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

 

---

연속합이 가장 큰부분을 찾아주면 되는 아주 간단한 문제!

 

어떻게 풀까 고민하다가

연결되는 숫자의 갯수별로 배열을 만들고 각각의 가장 큰값만 저장하도록 하게하는 방법을 생각해보았습니다.

 

그렇게 되면 시작위치에서 1개, 2개, 3개,..... n-시작위치 개 까지 계속 더해주면서 비교, 저장해주면 될것 같습니다!

 

 

일단 시작

 

---

어떻게 풀어 주긴했는데 시간초과 나네요....

 

10만개의 원소를 1~10만번 보는게 문제인것 같습니다.. 

#include <iostream>
#include <algorithm>

#include <vector>
#pragma warning(disable:4996)
using namespace std;

vector <int> numbers;

long long dp[100001]={0}; //갯수별 최대합 저장위치

void cal() {
    long long sum;
    for (int i = 0; i < numbers.size(); i++) {// 시작위치
        sum = 0;
        if (numbers[i] > 0) {
            for (int j = i; j < numbers.size(); j++) {
                sum += numbers[j];
                if (dp[j - i + 1] < sum) {
                    dp[j - i + 1] = sum;
                }
            }
        }
    }

}

int main() {
    int n;
    int num;
    long long answer = -1000;
    long long max_num = -1000;
    scanf("%d", &n);
    
    while (n--) {
        scanf("%d", &num);
        numbers.push_back(num);
        dp[n] = -1000;//필요없는 부분
        if (max_num < num) {
            max_num = num;
        }
    }

    dp[1] = max_num;// 제일 최솟값


    cal();

    for (int i = 0; i < numbers.size(); i++) {
        if (answer < dp[i]) {
            answer = dp[i];
        }
    }
    cout << answer << endl;
}

 

다른방법으로! 

 

좀더 실행시간을 줄여줄수있는 방법으로...

 

dp에 현재 숫자와 전번대의 최대합+현재숫자 를 비교 후 저장

계속 비교 저장!

 

dp[1]=int (dp[0]+n[1],n[1] )

dp[2]=int (dp[1]+n[2],n[2] )

.

.

.

.

 

 

계속 반복해줍시다

 

 

 

위에서 제가 풀었던 풀이와는 완전히 다른게

 

이 풀이에서의 dp에서는 전번대에서의 최댓값을 저장하는 것만 해주고

현재숫자를 연결할때와 연결하지 않을때를 나누어 생각 해주기위한? 용도로만 사용됩니다!

 

그렇기 때문에

answer값을 계속 해서 현재 dp 값과 비교해서 최댓값을 최신화 해줍시다.

 

 

 

코드는 아래와  같이 간단하게 나오게됩니다.

#include <iostream>
#include <algorithm>
using namespace std;
int N[100000];
int dp[100000];
int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> N[i];
	}

	dp[0] = N[0];
	int answer = dp[0];

	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + N[i], N[i]);
		answer = max(answer, dp[i]);
	}
	cout << answer << endl;
}

 

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!