백준 2670 연속부분최대곱

작성일 | In |

Problem : 연속부분최대곱

유형 : 다이나믹 프로그래밍

문제 설명

표

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

예제 입력

1
2
3
4
5
6
7
8
9
8
1.1
0.7
1.3
0.9
1.4
0.8
0.7
1.4

예제 출력

1
1.638

해결 전략

dp[num]에서 num에는
num을 마지막 인덱스로 하는 연속곱중
최대값을 저장 해둔다.

주의할 점

  • 3번 인덱스가 0인경우, dp[3]은 이러나 저러나 0이 될 것이다.
  • 4번 인덱스의 경우, dp[3]을 곱한것보다 자기 자신이 더 큰경우, 그곳부터 연속곱의 최대값을 구해 나간다.
  • 소수점 이하 셋째 자리까지 출력해야 한다.

풀이

숫자를 입력 받는다.

  • 한번도 연속으로 곱하지 않는경우가 답이 될 가능성이 있으므로
  • 초기 최대값 세팅은 입력받는 수 가운데 가장 큰 수로 해둔다.

각 구간까지 곱할때 최대의 값을 구한다.

  • dp[i] = max(dp[i], dp[i] * dp[i - 1]);

소수 점 이하 셋째 자리까지 출력해야 한다.

  • cout << fixed;
  • cout.precision(3);
  • 소수점 이하 출력포맷을 정해준다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define MAX 10001
using namespace std;

double dp[MAX], answer;
int n;

void ouput() {
	cout << fixed;
	cout.precision(3);
	cout << answer;
}

void solve() {
	for (int i = 1; i < n; ++i) {
		dp[i] = max(dp[i], dp[i] * dp[i - 1]);
		answer = max(answer, dp[i]);
	}
	ouput();
}

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> dp[i];
		answer = max(answer, dp[i]);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);

	input();
	solve();

	return 0;
}

피드백

없음