[백준] 2670번 : 연속부분최대곱 – JAVA [자바]

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

2670번: 연속부분최대곱

 

---

• 문제

​

---

• 문제 풀이

백준 2670번 연속부분최대곱 문제는 DP를 이용한 실버 4 난이도의 문제이다. 이 문제는 정답 비율이 35.866% (2022년 4월 5일 기준)으로 실버 4 난이도의 문제 치고는 낮은 편이다. 내가 생각했을 때는 아마도 소수점을 셋째 자리까지 반올림하고 출력하는 부분에서 사람들이 많이 틀리지 않나 싶다. 나도 처음에는 여기서 틀렸었다.

 

이번 문제는 1차원 dp 테이블을 만들어서 풀 수 있다. 이 문제에서 주어지는 수는 정수가 아닌 실수이기 때문에 int형 대신 double형을 써야 한다.

 

먼저 주어지는 입력을 double형 배열 arr에 입력받는다.

그리고 i번째 연속 부분 중의 최댓값을 double형 배열 dp에 저장한다. 

 

따라서, 다음과 같이 쓸 수 있다.

dp[i] = Math.max (arr[i], dp[i-1] * arr[i]);

 

문제에서 주어진 예시를 통해 한번 보겠다.

우선, 주어지는 입력은 다음과 같다.

 

우선 첫 번째 인덱스의 dp값, 즉 dp [1]은 당연히 arr [1]과 같다.

 

dp [2] = Math.max (dp [1] * arr [2], arr [2])이다. 즉, 1.1 * 0.7 = 0.77 > 0.7 이므로 dp [2]에 0.77을 저장한다.

 

dp [3]도 마찬가지로 한다. 1.3 > 0.77 * 1.3 = 1.001 이므로 1.3을 dp [3]에 저장한다.

 

dp [4] = Math.max(dp [3]*arr [4], arr [4])인데 1.3 * 0.9 = 1.17 > 0.9 이므로 1.17을 dp [4]에 저장한다.

 

1.17 * 1.4 = 1.638 > 1.4 이므로 dp [5]에 1.638을 저장한다.

 

dp [6] = Math.max(dp [5]*arr [6], arr [6])인데 1.638 * 0.8 = 1.3104 > 0.8 이므로 1.3104를 dp [6]에 저장한다.

 

dp [7] = Math.max(dp [6]*arr [7], arr [7])인데 1.3104 * 0.7 = 0.9173 > 0.7 이므로 0.9173을 dp [7]에 저장한다.

ㅇ

dp [8] = Math.max(dp [7]*arr [8], arr [8])인데 1.4 > 0.9173 * 1.4 = 1.2842 이므로 1.4를 dp [8]에 저장한다.

 

따라서 dp 값들 중에 최댓값인 1.638을 출력한다. 단, 문제에서는 최댓값을 셋째 자리까지 반올림해서 출력해야 하므로 String클래스의 format 함수를 이용해야 한다.

 

다음과 같이 코드를 작성하면 소수점 셋째 자리까지 반올림한 수를 String형으로 구할 수 있다.

 

String str = String.format("%.3f", number);

 

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        double[] arr = new double[n+1];
        double[] dp = new double[n+1];
        double max = 0;
        for (int i = 1; i <= n; i++) {
            arr[i] = Double.parseDouble(br.readLine());
            dp[i] = Math.max(arr[i], dp[i-1] * arr[i]);
            max = Math.max(max, dp[i]);
        }
        System.out.print(String.format("%.3f",max));
    }
}

 

---

• 후기

문제 자체의 난이도는 어렵지 않았지만 이 문제에서 String.format()이라는 함수를 배워서 되게 유익한 문제였던 거 같다.