백준 2670 - 연속부분최대곱

문제

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

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

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

해설

평이한 DP 문제이다. 찬찬히 생각해보지 않고 성급하게 시도하면 2차원 배열을 통한 메모이제이션을 할 수도 있는데, 1차원 배열로도 충분하다. 일단 연속적으로 곱셈을 한다는 점을 생각해보자. 해당 인덱스가 가질 수 있는 최댓값을 순차적으로 계산하여 진행하면 자연스럽게 최댓값을 탐색하게 된다.

전체적인 코드는 이렇다. 출력에서 자릿수를 맞춰야 하는 점을 유의하자.

auto n = 0;
auto v = std::vector<double>();

std::cin >> n;
v.reserve(n);

for (auto _ = 0; _ < n; _++) {
	auto tmp = 0.0;
	std::cin >> tmp;
	v.push_back(tmp);
}

auto big = v[0];

for (auto i = 1; i < v.size(); i++) {
	auto tmp = v[i] * v[i - 1];

	v[i] = std::max(v[i], tmp);
	big = std::max(v[i], big);
}

std::cout << std::fixed;
std::cout.precision(3);
std::cout << big;