알고리즘/동적 프로그래밍
[BOJ 2670] 연속부분최대곱 (Java, DP)
leejinwoo1126
2023. 6. 28. 23:12
반응형
문제 링크
https://www.acmicpc.net/problem/2670
2670번: 연속부분최대곱
첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나
www.acmicpc.net
문제 풀이
- 시간복잡도 O(N)
- DP 배열의 경우 이전 값과 곱한 경우와 자기 자신과 비교했을 때 더 큰 값을 갱신
| 1 | 2 | 3 | 4 | 5 |
| 1.1 | 0.7 | 1.3 | 0.9 | 1.4 |
| 1.1 | 0.77 | 1.3 | 1.117 | 1.638 |
*참고. 자바 소수점 처리
[Java] 자바 소수점 원하는 자리수 만큼 출력
자바로 문제를 풀다보면 소수점 몇째 자리까지 출력하라는 조건이 종종 나오곤 한다. double형의 두 수인 5.0과 3.0을 나눈 값을 출력하면 우측처럼 1.6666666666666667로 출력 가장 끝부분 다음 자리에
bullie.tistory.com
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static double[] DATA, DP;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
DATA = new double[N];
for(int i = 0; i < N; i++) {
DATA[i] = Double.parseDouble(br.readLine());
}
DP = new double[N];
}
static void pro() {
DP[0] = DATA[0];
for(int i = 1; i < N; i++) {
DP[i] = Math.max(DATA[i], DP[i - 1] * DATA[i]);
}
System.out.printf("%.3f", Arrays.stream(DP).max().getAsDouble());
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}반응형