[백준 2670] 연속부분최대곱

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

2670번: 연속부분최대곱

// 시간복잡도 : O(N)
// 권장
#include <cstdio>
int N;
double num[10000 + 10];
double max;

void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lf", &num[i]);
	}
}

void get_max(void)
{
	double tmp = 1;
	for (int i = 0; i < N; i++) {
		if (tmp <= 1) tmp = num[i];	// tmp가 1보다 작거나 같으면 바로 지금 원소부터 다시 곱하는 것이 낫다. 
		else tmp *= num[i];	// tmp가 1보다 크면 숫자를 곱하여 더 큰 수를 만든다.

		max = (tmp > max) ? tmp : max;
	}
}

int main()
{
	input();
	get_max();
	printf("%.3f", max);
	return 0;
}

//시간복잡도 : O(n^2)
#include <stdio.h>
int n;
double num[10000 + 2];

void input(void)
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lf", &num[i]);
	}
}	


double find_max(void)
{
	double max = 0;	double tmp;
	for (int i = 0; i < n; i++) {
		tmp = 1;
		for (int j = i; j < n; j++) {
			tmp *= num[j];
			if (tmp > max) max = tmp;
		}
		//printf("%.3f %.3f\n", tmp, max);
	}
	return max;
}

void main(void)
{
	input();
	double ans = find_max();
	printf("%.3f", ans);
}

이 문제는 두번째 방법을 생각하기 쉽지만.... 시간복잡도가 O(n^2)이 나올 수 있다는 점을 고려해야 한다.

주어지는 N이 만약 100,000이상의 수 라면 계산 시간이 어마어마하게 많이 소요될 것이다. 

그래서 첫번째 방법으로 푸는 것을 추천한다. 

 

간단히 설명하자면, 첫번째 방법의 키는 "tmp가 1보다 크면 곱하여 큰 수를 만들고, 1보다 거나 같으면 바로 그 숫자부터 다시 배열의 원소를 곱해나간다"이다. 

문제의 예시를 살펴보면, (1.1)  (0.7)  (1.3).... 이런식으로 숫자가 나열되어있을 때, (1.3)의 입장에서는 tmp = (1.1) * (0.7) 을 곱하는 것 보다 1.3 자신부터 숫자를 곱해나가는 것이 이득이다. 따라서 tmp > 1 인 경우 수열의 숫자를 곱해주고, tmp <= 1 인 경우는 자기 자신으로 tmp를 초기화 해준다.