[맞음] 백준 1912 연속합 c++ // dp, 규칙발견, ox를 그때그때 선택해버리기

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

1912번: 연속합

1 . ox를 그때그때 선택해버리기

1.완탐 : i번째수를 선택함, 안함으로 2^n 탐색해야함

2. 선택한경우 vs 선택안한경우에서 최적인 경우를 그때그떄 선택한다.

 

3. 이전값 + 현재값() vs 현재값(나부터 연속합 새로시작)  중에 큰값을 선택하면 된다.

 

2.전체코드

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

long long d[100004], a[100004],n;
//d[i]: i자리까지 연속합중 최대값 

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

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		d[i] = a[i];
	}

	d[1] = a[1];

	for (int i = 2; i <= n; ++i) {
		d[i] = max(a[i], d[i - 1] + a[i]);
		//d[i]=max(현재값[새로시작], 이전값+현재값)
	}

	//각각 i자리까지의 최대값이 저장됨
	//d[n]이 최대값 보장이아님 -> 최대값찾으면됨.
	cout << *max_element(d + 1, d + n + 1);
}

 

* 25.2.17 내 풀이 (dp)

• 다버리고 나부터 새로시작 vs 이전걸 이어받을건지 비교

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

int n;
int dp[100000+4], a[100000+4];

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   cin>>n;
   for(int i=0;i<n;++i) {
      cin>>a[i];
   }

   dp[0]=a[0];
   for(int i=1;i<n;++i) {
      if(dp[i-1]+a[i] < a[i]) {
         dp[i]=a[i];
      }
      else {
         dp[i]=dp[i-1]+a[i];
      }
   }

   cout<<*max_element(dp,dp+n);
}

 

* 큰돌풀이(그리디)

• 누적합이 음수라면 버리는 방식

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, sum, a, ret = -1001; 
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &a);  
        sum += a; 
        ret = max(ret, sum); 
        if(sum < 0) sum = 0;   
    } 
    printf("%d\n", ret);
    return 0;
}