[C++] 백준(BOJ) - 2670 : 연속부분최대곱

04 Apr 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 2670 : 연속부분최대곱(링크)

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

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

입력

첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 같고, 9.9보다 작거나 같다.

출력

계산된 최댓값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다.

알고리즘

1. 그리디
2. DP

풀이

• 점화식을 세워본다
• 초기값 기준으로 몇가지 케이스로 나눠서 예시를 들어서 로직이 맞는지 판단
• 전체 로직을 만들고 정답을 도출해낸다

코드

// BOJ - 2670 : 연속부분최대곱
#include <bits/stdc++.h>
using namespace std;

int n;
double a[10004], res;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	double b = a[0];
	res = b;

	for (int i = 1; i < n; i++)
	{
		if (a[i] > b * a[i]) b = a[i];
		else b *= a[i];
		res = max(b, res);
	}

	printf("%.3lf", res);

	return 0;
}

평가

• 연속된 수의 곱을 갱신해나가다 연속된 수의 곱보다 입력된 숫자를 사용한 것이 문제 조건을 이기는 경우 수를 갱신
• DP적인 풀이법