[BOJ] 2670 - 연속부분최대곱

Sierra·2022년 2월 8일
0
post-thumbnail

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

문제

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


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

입력

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

출력

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

예제 입출력

  • 예제 입력 1
8
1.1
0.7
1.3
0.9
1.4
0.8
0.7
1.4
  • 예제 출력 1
1.638

Solution

#include <iostream>
#define MAX 10001
using namespace std;

double DP[MAX];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> DP[i];
    double answer = DP[1];

    for(int i = 2; i <= N; i++){
        if(DP[i] * DP[i-1] >= DP[i]){
            DP[i] = DP[i] * DP[i-1];
        }
        answer = max(answer, DP[i]);
    }
    cout << fixed;
    cout.precision(3);
    cout << answer << '\n';
}

모든 입력값들을 DP테이블에 우선 저장한다. 그리고 탐색 값이 이전 DP 테이블값과 자신을 곱한것보다 크거나 같다면 해당 DP 테이블을 해당 값으로 갱신해준다.

어차피 구간 범위를 찾는게 아니라 해당 구간에서 계산을 진행한 값을 찾는것이기 때문에 그냥 무식하게 접근하면 풀리는 문제다.

profile
블로그 이전합니다 : https://swj-techblog.vercel.app/

0개의 댓글