[백준 C++] 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

알고리즘

• 이 문제는 다이나믹 프로그래밍 알고리즘을 사용하여 해결할 수 있다.
• 주어진 입력에 해당하는 크기가 동일한 배열을 한 개 만들어준다.
  (이 배열은 현재 자신의 위치까지의 최대 곱을 나타내는 배열이다.)
• 자기 자신의 값과 자신의 뒤에 있는 숫자까지의 최대 곱을 곱해 더 크다면 그 값을 최대 곱 행렬에 추가하고 자기 자신이 더 크다면 자기 자신을 최대 곱 행렬에 추가해준다.
• 예제 1번을 예를 들어 설명하자면,

1. 1.1은 앞에 곱해줄 값이 없으므로 1.1이 최대 곱 행렬에 들어감
2. 0.7과 1.1을 곱한 값 0.77은 0.7보다 크므로 0.7까지의 최대 곱은 0.77이 됨
3. 0.77과 1.3을 곱한 값 1.001은 1.3보다 작으므로 이 위치에서는 앞의 값과 곱한 값이 아닌 자기 자신이 최대 곱이 됨

• 이러한 방법으로 최대 곱 행렬을 구해준 뒤 최대 값을 찾으면 된다.

#include <iostream>
#include <vector>

using namespace std;

int main(void) {

	int N;
	double temp, max = 0;
	vector<double> number, result;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> temp;
		number.push_back(temp);
	}

	result.push_back(number[0]);
	max = number[0];

	for (int i = 1; i < N; i++) {
		if (number[i] * result[i - 1] >= number[i]) temp = number[i] * result[i - 1];
		else temp = number[i];

		result.push_back(temp);
		if (max < temp) max = temp;
	}

	cout << fixed;
	cout.precision(3);
	cout << max;

}