[백준 2670] 연속부분최대곱 (자바)

백준 2670번 연속부분최대곱 (자바)

 

 

 

출처

www.acmicpc.net/problem/2670

2670번: 연속부분최대곱

 

 

 

문제

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

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

입출력 예

입출력 예 1

 

 

 

접근 방법

i부터 연속합을 구하려면 i+1부터 n까지의 곱을 구하면 되므로 2중 for문을 사용했다.

계속해서 곱하다가 1보다 작은 값을 곱하면 더 작아지므로 max함수를 사용해 최대값을 지속해서 넣어주도록 했다.

 

점화식 : dp[i] = max(dp[i], dp[i]*map[i+1] ... dp[i]*map[n]) 

 

소수를 곱하기 때문에 자료형은 float이나 double을 사용해야 한다.

문제의 최대 조건인 10000을 넣은 경우 float로 다 담을 수 없기 때문에 double을 사용하자.

 

 

 

 

내 코드

 

 

 

 

 

고려할 점

1. 규칙을 찾아 점화식을 세울 것

2. 소수점을 고려할 것