[백준 2670] 연속부분최대곱 (자바)
백준 2670번 연속부분최대곱 (자바)
출처
2670번: 연속부분최대곱
N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면, 색칠된
www.acmicpc.net
문제
N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면,
색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.
입력
첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어진다.
출력
계산된 최댓값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다.
입출력 예
접근 방법
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. 소수점을 고려할 것