[Algorithm]Baekjoon 2670번 :: 연속부분최대곱

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

2670번: 연속부분최대곱

 
 
int n;
double arr[10001];
double leftCumulativeProducts[10001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    double result = 0.0f;
    double cumulativeProduct = result = leftCumulativeProducts[0] = arr[0];
 
    for (int i = 1; i < n; ++i)
    {
        cumulativeProduct = max(cumulativeProduct * arr[i], arr[i]);
        leftCumulativeProducts[i] = cumulativeProduct;
        result = max(result, cumulativeProduct);
    }
 
    printf("%.3lf", result);
}
 
 
 

 

'연속된 구간' 중에서 최대의 누적곱을 구해야하는 문제이다.

이전에 상위호환의 문제를 푼적이 있어서 쉽게 풀 수 있었다.

값을 이어나가는 시도를 할건데, 만약 값을 이으는것보다(연속되어지는 것보다), 아예 새로 출발하는게 더 이득일 경우 새로 출발하는것을 선택하면 된다.

 

그리고 유의할점은, float자료형보다는 double을 써야한다. 아마 표현할 수 있는 정밀도개수차이 때문에 그런 것 같다.

float으로 제출하면 틀리고, double로 제출해야 통과한다.