BOJ(C++) / 백준 2670 : 연속부분최대곱

백준 2670 : 연속 부분 최대곱

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

2670번: 연속부분최대곱

 

문제

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

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

 

입력

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

 

출력

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

 

코드

//백준 2670 연속부분최대곱
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

	int N;
	cin >> N;
	vector<double> v;
	for (int i = 0; i < N; i++) {
		double num;
		cin >> num;
		v.push_back(num);
	}
	
	double dp[10001] = { 0.0, };
	double M = 0.0;
	dp[0] = v[0];
	for (int i = 1; i < N; i++) {
		dp[i] = max(v[i], v[i] * dp[i - 1]);
		M = max(M, dp[i]);
	}

	printf("%.3f", M); //소수점 세자리
	//cout << lround(M * 1000) / 1000.0 << "\n"; //반올림

	return 0;
}

 

설명

DP(다이내믹 프로그래밍) 문제이다.

dp 배열에 이전까지 최대가 되는 부분을 곱하여 최댓값을 저장한다. 

 

고찰

처음에 완전 탐색으로 모든 곱을 구하여 곱이 최대가 되는 값을 구했었는데 3중 반복문을 쓰다 보니 시간 초과가 뜨게 되었다. 구글링 후 DP문제라는 것을 알고 DP로 접근하여 문제를 풀 수 있었다.

 

소수점 이하 넷째 자리에서 반올림

printf("%.3f", M); //소수점 세자리

#include <cmath>
cout << lround(M * 1000) / 1000.0 << "\n"; //반올림

반올림은 다음과 같은 방법으로 구할 수 있다. 

 

난이도

Silver 4