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

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

2670번: 연속부분최대곱

코드설명

DP 문제입니다.

 

DP[N] : 각 인덱스에서 최대의 연속부분최대곱 으로 선언합니다.

만약 DP[2] < DP[1] * DP[2] 라면 DP[2] = DP[1] * DP[2] 가 됩니다.

만약 DP[2] >= DP[1] * DP[2] 라면 DP[2] = DP[2] 입니다.

 

8
1.1
0.7
1.3
0.9
1.4
0.8
0.7
1.4

 

DP를 출력해보면,

1.1
0.77
1.3
1.1700000000000002
1.6380000000000001
1.3104000000000002
0.9172800000000001
1.4

위와 같이 각 위치에서 연속된 부분의 최대곱을 구하고 있습니다.

 

문제에서 유의할점은 double 형을 써야 소수점의 값들이 계산됩니다.

처음에 float로 사용하여 소수점 7자리까지 연산하니 값이 온전히 검사되지 않습니다. float는 4바이트(32bit)의 수까지 표현

그렇기에 double을 사용하여 소수점 15자리까지 연산함으로써 통과했습니다. double은 8바이트 (64bit)의 수까지 표현

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N;
	public static double answer = 0;
	public static double[] map;
	public static double[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new double[N];
    	dp = new double[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = Double.parseDouble(st.nextToken());
    		dp[i] = map[i];
    	}
    	
    	dp[0] = map[0];
    	for(int i=1;i<N;i++) {
    		
    		if(dp[i] < dp[i] * dp[i-1]) {
    			dp[i] = dp[i] * dp[i-1];
    		}
    		
    	}
    	
    	for(int i=0;i<N;i++) {
    		answer = Math.max(answer,  dp[i]);
    	}
    	
    	
    	System.out.println(String.format("%.3f", answer));
    }
    
    
}