문제
N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면,
색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.
첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 같고, 9.9보다 작거나 같다.
계산된 최댓값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다.
[풀이 코드]
import java.io.*;
import java.util.*;
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[] arr = new double[N];
double value = 1;
for (int i = 0; i < N; i++) {
arr[i] = Double.parseDouble(br.readLine());
}
double cur = arr[0];
double max = arr[0];
for (int i = 1; i < N; i++) {
cur = Math.max(arr[i], cur*arr[i]);
max = Math.max(max, cur);
}
System.out.printf("%.3f", max);
}
}이 문제는 DP다. 왜냐하면 현재 위치에서 만들 수 있는 최대 연속 곱의 값은 이전 위치까지의 최대 연속 곱 값에 영향을 받기 때문이다.
cur은 이전 값에 현재 값을 곱한 값과 현재 값을 비교한 값 중 가장 큰 값을 가진다.
예를 들어, 반복문에서 현재 3번째 인덱스에 있다고 했을 때, 0, 1, 2, 3번째 인덱스에 있는 값을 곱한 값과 3번째 인덱스에 있는 값을 비교한다.
전자일 경우, 다음에는 0~4번째 인덱스에 있는 값을 곱한 값과 4번째 인덱스에 있는 값을 비교할 것이고,
후자일 경우, 3~4번째 인덱스에 있는 값을 곱한 값과 4번째 인덱스에 있는 값을 비교할 것이다.
max는 현재 값과 cur에 있는 값 중 큰 값을 비교한다.
DP문제는 많이 풀어봐야 감이 온다고 들었다. DP를 많이 풀어보자!!!
