[자바]백준 2670번 연속부분최대곱 [다이나믹프로그래밍][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

문제 링크

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

2670번: 연속부분최대곱

문제 설명

위의 문제는 N개의 양의 실수가 나열이 되어있는 수열 중에 차례대로 연속된 수들이 곱들 중에 최댓값을 찾는 문제이다.

해설

핵심은 dp에 순간순간의 최대값을 기록해 주면 된다.

순간순간 현재 값이나 현재값 전에 dp값과 곱한 것 중에 최댓값이 dp에 기록되는 것이다.

 

해당 문제는 곱들의 최대가 되는 길이를 파악하는 문제가 아니기 때문에 어렵지 않게 풀 수 있다.

• A(0) ~ A(n)의 값을 갖고 있는 배열을 순차적으로 탐색하기 
• A(0)은 A(0)이 최대값이고
• A(1)은 A(1)과 A(0) * A(1) 둘 중에 큰 값을 넣어준다.
• ...
• ...
• 이런 식으로 A(n)까지 구하면서 최댓값을 파악하면 된다.

참고

한 가지 중요한 점이 있는데 출력에서 요구사항 중 하나가 소수점 셋째 자리까지 출력하는 것이다.

그래서 Math.round(max * 1000) % 1000.0을 사용하면, 답이 정수이면 소수점 한자리만 출력되기 때문에 format 형식을 사용하여 셋째 자리까지 잡아주는 게 좋다.

 

예를 들어, 답이 1이면 1.000을 출력해야 하는데 1을 float이나 double로 잡고 출력하면 1.0으로 출력되어 답이 틀리게 된다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        double[] dp = new double[N];

        dp[0] = Double.parseDouble(br.readLine());

        double max = dp[0];

        for (int i = 1; i < N; i++) {
            double num1 = Double.parseDouble(br.readLine());
            double num2 = dp[i - 1] * num1;
            
            dp[i] = Math.max(num1, num2);
            
            max = Math.max(max, dp[i]);
        }

        System.out.printf("%.3f\n", max);
        br.close();
    }
}