[백준 BOJ] 2670번 연속부분최대곱 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 브루트포스 알고리즘을 활용한 DP 기초 문제

백준의 2670번 문제는 브루트포스 알고리즘을 활용한 다이나믹 프로그래밍의 기초 활용 문제이다.

해당 문제는, 주어지는 실수형 수열에 대하여 하나 이상의 연속된 수들의 곱이 최대가 되는 값을 찾아 이 결괏값을 정답으로 출력해야 하는 문제이다.

이때 출력 조건을 확인해 보면, 소수점 넷째 자리에서 반올림하여 소수점 3번째 자리까지 정답을 출력하라는 점을 알 수 있다.

 

우선은 2가지 알고리즘 용어의 정의부터 짚어본 뒤, 이후에 문제 해결 원리를 설명하는 것이 좋을 듯하다.

브루트포스 알고리즘이란, 가능한 모든 경우에 대한 연산을 시도해 보며 정답을 탐색하는 알고리즘을 뜻한다.

다이나믹 프로그래밍(DP)이란, 복잡한 문제를 중복되는 하위 문제로 쪼개어 해결해 나가는 알고리즘 설계 방법을 뜻한다.

위에 제시된 두 용어의 정의를 살펴보면, 이 문제는 쪼갤 수 있는 작은 문제들의 중복된 패턴을 찾아내고 그에 대한 모든 경우의 수를 고려해 정답을 구해야 한다는 점을 알 수 있다.

 

필자의 경우에는, 값을 하나씩 입력받을 때마다 이 위치의 값을 포함한 연속된 수들의 곱을 연산해 가며 정답인 곱연산의 최댓값을 찾아나가도록 코드를 설계하였다.

알고리즘의 구체적인 원리는 아래의 그림과 설명을 함께 참고해 보길 바란다.

(편의상, 예제 입출력 1에 있어 1번째 ~ 5번째 입력까지만 그림으로 표현해 보았다.)

* 1.1 입력받는 시점
=> 입력값이 1.1 뿐이기 때문에, 1.1을 포함한 곱 연산 결과로 나올 수 있는 수는 1.1 뿐이다.
=> 현재까지의 최대 곱은 1.1이다.

* 0.7 입력받는 시점
=> 0.7을 포함한 곱 연산 결과로 나올 수 있는 수는 각각 0.7과 0.77이 있다.
=> 현재까지의 최대 곱은 1.1이다.

* 1.3 입력받는 시점
=> 1.3을 포함한 곱 연산 결과로 나올 수 있는 수는 각각 1.3, 0.91, 1.001이 있다.
=> 현재까지의 최대 곱은 1.3이다.

* 0.9 입력받는 시점
=> 0.9를 포함한 곱 연산 결과로 나올 수 있는 수는 각각 0.9, 1.17, 0.819, 0.9009가 있다.
=> 현재까지의 최대 곱은 1.3이다.

* 1.4 입력받는 시점
=> 1.4를 포함한 곱 연산 결과로 나올 수 있는 수는 각각 1.4, 1.26, 1.638, 1.1466, 1.26126이 있다.
=> 현재까지의 최대 곱은 1.638이다.

...

위와 같은 방식으로 곱 연산 결과를 모두 도출하다 보면, 그중 가장 최댓값은 1.638로 나타난다.
이 값이 바로 해당 입력에 대한 정답이라 볼 수 있다.

 

보다 자세한 설명을 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다. 

 

코드의 실행 순서

1) 입력값의 개수(n)를 입력받는다.

 

2) 연속된 수들의 곱의 최댓값을 저장할 변수 result를 0으로 초기화하여 미리 선언해 둔다.

이에 더불어, 각 입력값들을 저장할 벡터 v를 선언해 둔다.

(입력값 및 곱 연산 결과 모두 실수형으로 주어질 예정이기 때문에, 이 둘 모두 double형으로 설정한다.)

 

3) n의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 값(num)을 하나씩 입력받는다. 입력을 받는 대로, 해당 값을 v의 요소로 삽입하도록 한다.

- 현재의 num값을 포함한 연속된 수들의 곱을 연산할 시에 활용할 임의의 변수 cnt를 1로 초기화하여 선언하도록 한다.

- 다른 반복문을 활용하여, v의 끝 요소부터 시작 요소까지 하여 하나씩 cnt에 값을 곱하도록 한다.

하나씩 곱할 때마다 각 시점에서의 cnt와 result 값을 비교해 주고, 만약 cnt가 더 큰 값을 가진다면 result를 현재 시점의 cnt 값으로 갱신하도록 한다.

 

4) 위 연산을 모두 완료하였다면, 최종적으로 저장된 result의 값을 정답으로 출력한 뒤 실행을 종료한다.

(문제의 조건을 만족하기 위하여, 필자는 아래 구문을 통해 정답을 소수점 3번째 자리까지 출력하게끔 하였다.)

cout << fixed;
cout.precision(3);

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

//백준 2670번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	cout << fixed;
	cout.precision(3);

	int n;
	cin >> n;

	double result = 0;
	vector<double> v;
	for (int i = 0; i < n; i++) {
		double num;
		cin >> num;
		v.push_back(num);

		double cnt = 1;
		for (int j = i; j >= 0; j--) {
			cnt *= v[j];
			if (cnt > result) {
				result = cnt;
			}
		}
	}

	cout << result << endl;
}

 

제출 결과

(2025.12.29 백준 2670번 문제 제출 결과)