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

짱수·2023년 3월 30일

알고리즘 문제풀이

목록 보기

10/26

🔒문제 설명

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

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

입력

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

출력

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

🔑해결 아이디어

DP를 사용하는 문제는 모두 어떤 값을 DP에 저장하는지에 따라 성능이 크게 달라진다.
이번 문제의 DP는 한번만 갱신하며, 각 DP는 이전 DP 값과 현재 수를 곱한 뒤 현재 수와 곱셈의 결과 중 큰 값을 저장한다.

오답노트

1. 자바 배열의 깊은 복사, 얕은 복사

처음 접근한 아이디어는 $O(n^2)$ 시간의 아이디어였다.
$i$ 번째로 갱신하는 DP[j]의 값은 $j-i$ 번째 숫자부터 $j$ 번째 숫자까지 $i$ 개의 숫자를 곱한 값을 저장하려고 했다.

double[] numbers;
// numbers 입력
double[] DP = numbers;
//...//

위와 같은 코드를 작성했었는데, 결과가 제대로 나오지 않았다.
테스트케이스의 결과값이 70이상의 수가 나와서 이상하게 생각했는데, 디버깅을 해 보니 numbers와 DP가 같은 메모리 공간을 가리키게 되면서 DP값을 수정하면 numbers까지 같이 수정이 되는 오류가 있었다.
얕은 복사는 클래스 단위로만 이루어 지는 줄 알았기 때문에 일어난 실수다.

해결 방법
각 원소를 반복문으로 탐색하면서 값 자체를 복사해 준다.

2. 부동 소수점의 오차범위

이번에는 50%에서 다시 틀렸다고 오류가 났다.
논리적으로는 오류가 없어서 한참을 고민했는데, 질문 글에서 힌트를 찾았다.

4
6.1
4.3
0.5
6.1

위의 입력 에서는 80.0015라는 계산 결과가 나오면서 80.002라는 출력이 나와야 했는데, 내 코드는 80.00149999999998 라는 계산 결과가 나오면서 80.001을 출력했다.
디버깅을 해 보니 6.1 * 4.3을 26.229999999999997로 계산하면서 오류가 발생한 것이다.

해결 방법
주어지는 소수는 모두 소수점 한자리까지만 존재하므로, 곱할 두 실수에 10을 곱해 정수의 곱셈을 수행한 이후 다시 100을 나누어 주는 방법으로 오차를 줄였다.

3. 연산 횟수 증가에 따른 오차 (?)

그래도 50% 실패가 해결되지 않았다.
문제가 해결되지 않아 다른 사람의 풀이를 찾아보니 $O(n)$ 시간으로 해결할 수 있는 훨씬 빠른 풀이가 존재했다.
해당 풀이 방법으로 다시 구현하여 성공할 수 있었다.
정확히 어떤 부분에서 오류가 났는지 확인할 수는 없었지만, 연산 횟수가 줄어듬에 따라 실수의 연산에서 나타날 수 있는 오차 범위가 줄었다고 예상한다.

💻소스코드

import java.util.Scanner;

public class BJ2670 {
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        double[] numbers = new double[n];
        for(int i = 0; i<n; i++) {
            numbers[i] = sc.nextDouble();
        }
        double[] DP = new double[n];
        for(int i = 0; i<n; i++)
            DP[i] = numbers[i];

        double max = DP[0];
        for(int i = 1; i<n; i++){
            double mult = DP[i - 1] * numbers[i];
            if(mult > numbers[i])
                DP[i] = mult;
        }

        for(int i = 0; i<n; i++)
            if(max < DP[i])
                max = DP[i];

        max = Math.round(max*1000)/1000.0;
        System.out.printf("%.3f",max);
    }
}