백준 2670 - 연속부분최대곱(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2670

2670번: 연속부분최대곱

연속된 수를 곱할 때, 나올 수 있는 최댓값을 구하는 문제입니다.

 

N은 10,000이하의 수이기에 2중 for문을 사용하면 시간초과가 생길 수 있습니다.

따라서 DP를 사용해서 지금까지 곱한 값의 최댓값을 저장해주면서 풀어나가면 됩니다.

 

문제를 풀기 위해 예시를 생각해보겠습니다.

4번까지 곱한 값의 최댓값을 구하기 위해선 2가지 방법이 있습니다.

1. 3번까지 곱한 값과 4번 자신의 값을 곱한다.

2. 4번 자신의 값을 그냥 가져온다.

1번과 2번 중, 더 큰값을 가져온다면 N번까지의 곱 중 가장 큰 값이 될 것입니다.

 

따라서 점화식은 다음과 같습니다.

dp[i] = max(dp[i-1] * arr[i], arr[i])

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N;
double arr[10001];
double dp[10001];

void solve(){
    dp[1] = arr[1];
    for(int i = 2; i <= N; i++){
        dp[i] = max(dp[i-1]*arr[i], arr[i]);
    }
    double maxi = 0.0;
    for(int i = 1; i <= N; i++){
        maxi = max(maxi, dp[i]);
    }
    printf("%.3f", maxi);
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> arr[i];
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요