[C++] 백준 2670 - 연속부분최대곱

문제 - 연속부분최대곱 (Silver 4)

[백준 2670] https://www.acmicpc.net/problem/2670

풀이 전략

• 다이나믹 프로그래밍 알고리즘을 이용하여 전까지의 계산 결과를 Dp 배열에 저장해 놓고, 다음 수를 곱한 새로운 값과 기존의 값을 비교하여 더 큰 값을 Dp의 현재 위치에 저장
• 계산이 모두 끝나면 오름차순으로 정렬한 뒤, Dp 배열의 제일 마지막 위치에 있는 값을 출력

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip> // 소수점 위치 고정용
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;

    vector<double> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    
    vector<double> Dp(N);
    
    Dp[0]=A[0]; // Dp 배열의 첫번째 값 초기화
    for (int i = 1; i < N; i++) {
        Dp[i]=max(A[i],Dp[i-1]*A[i]);
    } // 현재 값과 누적 곱을 비교하여 더 큰 값을 현재 위치에 저장
    sort(Dp.begin(),Dp.end());
   // 오름 차순으로 정렬 
    cout<<fixed<<setprecision(3)<<Dp[N-1]<<'\n';
    // 소수점 3자리로 설정한 뒤, Dp의 제일 마지막 값을 출력
    return 0;
}

결과