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

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

2670번: 연속부분최대곱

문제

N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면,

색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.

 

입력

첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 같고, 9.9보다 작거나 같다.

 

출력

계산된 최댓값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다.

 

풀이

다이나믹 프로그래밍 문제로, 누적 곱이 1이상일 경우 계속 곱하면서 저장하고

누적 곱이 1보다 작으면 곱하는 것을 멈추고 새로 시작한다. (1보다 작은 값과 곱하면 계속 작아질 것이기 때문)

된다.

 

답안코드

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

int N;
double D[10000 + 10];
double dp[10000 + 10];

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

double Solve() {
    dp[0] = D[0];

    double sol = D[0];

    for (int i = 1; i < N; i++)
    {
        if (D[i] * dp[i - 1] < D[i]) {  // 누적 곱 결과가 1보다 작으면 새로 시작(계속 곱해봤자 계속 작아짐)
            dp[i] = D[i];       
        }
        else {
            dp[i] = D[i] * dp[i - 1];   // 1이상이면 계속 곱하기
        }

        sol = max(sol, dp[i]);
    }

    return sol;
}

int main() {
    double ans = -1;

    InputData();

    ans = Solve();

    printf("%.3lf\n", ans);

    return 0;
}