KOI 1996 중등부 연속부분최대곱

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

첫번째 포스팅입니다.

한국정보올림피아드 1996년도 중등부 1번문제 연속부분최대곱 문제를 풀어봤습니다.

흔하디 흔한 dp(dynamic programming)으로 풀었습니다.

dp[i]는 i번째 수열에서 끝나는 부분수열의 최대곱을 저장합니다.

가령 arr이 원래 수열이라고 하면

i	0	1	2	3	4	5	6	7
arr	1.1	0.7	1.3	0.9	1.4	0.8	0.7	1.4
dp	1.1	0.77	1.3	1.17	1.638	1.3104	0.91728	1.4

dp[0]은 arr[0]

dp[1]는 arr[0] * arr[1]

dp[2]은 arr[0] * arr[1] * arr[2]

dp[3]은 arr[0] * arr[1] * arr[2] * arr[3]

dp[4]은 arr[0] * arr[1] * arr[2] * arr[3] * arr[4]

dp[5]은 arr[0] * arr[1] * arr[2] * arr[3] * arr[4] * arr[5]

dp[6]은 arr[0] * arr[1] * arr[2] * arr[3] * arr[4] * arr[5]

dp[7]은 arr[7]

이 됩니다.

dp[7]의 경우를 제외하고 항상 더 곱하는것이 좋은 결과를 가져오는데, dp[6]의 경우 1보다 작으므로, dp[7]에서는 이전 앞의 누적 곱을 제외하고 본인만 가져가는것이 이득이므로 dp[7] = arr[7]이 됩니다.

출력 시, 포맷 스트링으로 %.3lf를 사용하면 소수점 4번째 자리에서 자동 반올림된 값이 나타나는 것을 처음 알았네요.

반올림 된 값으로 출력만 할 경우 유용할 것 같습니다.

#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef double vt;

int N;
vector<vt> arr;
vector<vt> dp;

int main() {
	cin >> N;
	
	arr.reserve(N);
	dp.reserve(N+1);
	for (int i=0; i < N; i++) {
		vt val;
		cin >> val;
		arr.push_back(val);
	}
	dp[0] = arr[0];
	for (int i=1; i <= N; i++) {
		if (dp[i-1] > 1) {
			dp[i] = dp[i-1] * arr[i];
		} else {
			dp[i] = arr[i];
		}
	}
	vt max_val = -987654321;
	for (int i=0; i < N; i++) {
		max_val = max(max_val, dp[i]);
	}
	printf("%.3lf\n", max_val);
	
}