[세모] 백준 2670 연속부분최대곱 //완탐, dp, 그리디

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

* 풀이1 (N^2)

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

typedef long long ll;

int n;
double a[10000+4];
double ret;

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];
      ret = max(ret, a[i]); // 단일 요소도 체크!!!
   }

   for(int i=0;i<n;++i) {
      double sum=a[i];
      for(int j=i+1;j<n;++j) {
         sum *= a[j];
         ret=max(ret,sum);
      }
      
   }
   cout<<fixed<<setprecision(3);
   cout<<ret;
   
}

• for(int j = i+1)
  • 단점 : 단일요소 체크를 추가로 넣어줘야함

 

* 풀이2 (N^2)

• for(int j=i ~)
  • 장점 : 단일요소 체크를 포함함

 

* 풀이3 (NlogN)

• 그리디? dp?

• 주의 : dp[n-1]이 답이아님
  • 중간범위에 최대값이 있을수있음
  • 계산할때마다 ret 갱신필요

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

typedef long long ll;

int n;
double a[10000+4]; //원본
double dp[10000+4]; // 
double ret;

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];
   ret=a[0];
   for(int i=1;i<n;++i) {
      double gob = dp[i-1] * a[i];
      if(gob < a[i]) {
         dp[i]=a[i];
      }
      else {
         dp[i] = gob;
      }
      ret=max(ret,dp[i]);
   }
   cout<<fixed<<setprecision(3);
   cout<<ret;
   //dp[n-1]이 안되는이유
   //중간 범위에 최대값이 있을수 있음
   // -> 계산할때마다 ret 갱신해줘야함
}

• 큰돌풀이
  • dp[]대신
  • b 변수하나로 할수 있음

#include <bits/stdc++.h>
using namespace std; 
int n;
double psum[10001], a[10001], ret, b;
int main(){
	cin >> n; 
	for(int i = 0; i < n; i++) cin >> a[i]; 
	double b = a[0];
	for(int i = 1; i < n; i++){
		if(a[i] > b * a[i])b = a[i];
		else b *= a[i];
		ret = max(b, ret);
	} 
	printf("%.3lf", ret + 0.00001); 

	return 0;
}