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

이번에는 백준 2670번 연속부분최대곱 문제를 풀어보았습니다.

연속된 수들의 곱을 구해야 하므로, 각 위치에서 이전까지 이어온 곱에 현재 값을 곱할지, 아니면 현재 값부터 새롭게 시작할지를 비교하면 됩니다.

현재 값부터 다시 시작하는 편이 더 크다면 이전까지의 곱을 버리고, 그렇지 않다면 계속 곱해가면서 최댓값을 갱신하는 방식으로 해결하였습니다.

---

문제 설명

N개의 실수가 주어졌을 때, 한 개 이상의 연속된 수를 선택하여 그 곱의 최댓값을 구하는 문제입니다.

예를 들어

1.1 0.7 1.3 0.9 1.4

와 같은 수열이 있을 때, 연속된 구간 중 곱이 가장 큰 경우를 찾아야 합니다.

중간의 수를 건너뛸 수는 없으며 반드시 연속된 부분 수열이어야 합니다.

---

풀이 아이디어

현재 위치의 값이 arr[i]라고 할 때 두 가지 경우를 비교합니다.

이전까지 이어온 곱 × arr[i]
arr[i]부터 새롭게 시작

만약

cur × arr[i] < arr[i]

라면 이전까지의 곱을 이어가는 것보다 현재 값부터 새롭게 시작하는 것이 더 큽니다.

따라서

cur = arr[i];

로 갱신합니다.

반대로 이전까지의 곱을 이어가는 것이 더 크다면

cur *= arr[i];

로 계속 곱해줍니다.

각 위치마다 만들어지는 cur 중 가장 큰 값을 ret에 저장하면 됩니다.

---

코드

#include <bits/stdc++.h>
using namespace std;
double arr[10000];
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    for(int i=0; i<N; i++) {
        cin >> arr[i];
    }

    double ret = arr[0];
    double cur = arr[0];
    for (int i=1; i<N; i++) {
        if (cur * arr[i] < arr[i]) {
            cur = arr[i];
        } else {
            cur *= arr[i];
        }
        ret = max(cur, ret);
    }

    cout << fixed << setprecision(3) << ret << '\n';
    return 0;
}

---

풀이 흐름

1. N개의 실수를 입력받습니다.

2. 첫 번째 값을 cur과 ret의 초기값으로 설정합니다.

3. 두 번째 값부터 순회합니다.

4. 이전까지 이어온 곱에 현재 값을 곱한 값과 현재 값 자체를 비교합니다.

5. 현재 값 자체가 더 크다면 이전 구간을 버리고 현재 위치부터 새롭게 시작합니다.

6. 그렇지 않다면 기존 연속 구간에 현재 값을 포함합니다.

7. 매 위치마다 ret을 갱신합니다.

8. 최종 최댓값을 소수점 셋째 자리까지 출력합니다.

---

구현 포인트

1. cur의 의미

double cur = arr[0];

cur에는 현재 위치를 마지막 원소로 가지는 연속 부분 수열 중 곱이 가장 큰 값이 저장됩니다.

즉, 현재 위치까지 왔을 때

이전 구간을 계속 이어갈지
현재 위치부터 새롭게 시작할지

결정한 결과가 cur입니다.

---

2. 현재 값부터 새롭게 시작하는 경우

if (cur * arr[i] < arr[i]) {
    cur = arr[i];
}

이전까지의 곱에 현재 값을 곱한 결과보다 현재 값 자체가 더 크다면 기존 구간을 이어갈 필요가 없습니다.

예를 들어

cur = 0.4
arr[i] = 2.0

이라면

0.4 × 2.0 = 0.8

이지만 현재 값 자체는

2.0

입니다.

따라서 이전까지의 값들을 포함하지 않고 현재 위치부터 다시 시작하는 것이 더 큰 곱을 만들 수 있습니다.

---

3. 이전 구간을 이어가는 경우

else {
    cur *= arr[i];
}

이전까지의 곱에 현재 값을 곱한 결과가 더 크거나 같다면 기존 연속 구간을 유지합니다.

예를 들어

cur = 1.5
arr[i] = 1.2

라면

1.5 × 1.2 = 1.8

이 현재 값 1.2보다 크므로 이전 구간을 계속 이어가는 것이 유리합니다.

---

4. 두 경우를 비교하는 이유

각 위치에서 만들 수 있는 최댓값은 결국 다음 두 가지 중 하나입니다.

현재 값부터 시작
이전까지의 최댓값 × 현재 값

즉,

cur = max(arr[i], cur × arr[i])

와 같은 의미입니다.

코드에서는 이를 if문으로 나누어 구현하였습니다.

---

5. 전체 최댓값 갱신

ret = max(cur, ret);

cur은 현재 위치에서 끝나는 연속 부분 수열의 최대 곱입니다.

하지만 전체 정답이 반드시 마지막 위치에서 끝나는 것은 아닙니다.

따라서 매 위치마다 지금까지 나온 최대값과 비교하여 ret을 갱신합니다.

---

6. 첫 번째 값으로 초기화

double ret = arr[0];
double cur = arr[0];

문제에서는 한 개 이상의 연속된 수를 선택해야 합니다.

따라서 아무것도 선택하지 않은 값인 0이나 1로 시작하는 것이 아니라 실제 첫 번째 원소로 초기화합니다.

이렇게 하면 N = 1인 경우에도 정상적으로 처리할 수 있습니다.

---

7. 입력값에 0이 있는 경우

입력값은 0.0도 가능합니다.

예를 들어

2.0 0.0 3.0

이라면 2.0 × 0.0 = 0.0이 되므로 그 뒤의 3.0에서는

0.0 × 3.0 < 3.0

이 되어 자연스럽게 3.0부터 새로운 구간이 시작됩니다.

따라서 0을 별도로 처리할 필요가 없습니다.

---

8. 최대 부분합과 비슷한 형태

이 문제는 연속된 부분 구간을 유지할지 버릴지를 결정한다는 점에서 최대 연속 부분합 문제와 비슷합니다.

최대 부분합에서는

기존 합 + 현재 값
현재 값

을 비교했다면, 이 문제에서는

기존 곱 × 현재 값
현재 값

을 비교합니다.

입력값이 모두 0 이상이기 때문에 현재 위치에서 필요한 상태를 cur 하나만으로 관리할 수 있습니다.

---

9. 출력 형식

cout << fixed << setprecision(3) << ret << '\n';

문제에서는 소수점 넷째 자리에서 반올림하여 소수점 셋째 자리까지 출력해야 합니다.

fixed를 사용하면 고정 소수점 형태로 출력되고,

setprecision(3)

을 사용하면 소수점 아래 세 자리까지 출력할 수 있습니다.

예를 들어

1.6382

라면

1.638

으로 출력됩니다.

---

시간복잡도

입력을 받은 뒤 수열을 한 번만 순회합니다.

따라서 시간복잡도는

O(N)

입니다.

추가적인 탐색이나 정렬이 없으므로 N이 최대 10,000일 때 충분히 빠르게 해결할 수 있습니다.

배열에 N개의 실수를 저장하므로 공간복잡도는

O(N)

입니다.