[백준 2670번] 연속부분최대곱 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

이번 문제는 DP를 이용하여 풀이가 가능합니다.

 

문제 풀이에 앞서 입력으로 주어지는 N이 10,000 이하의 자연수 이므로 N은 10,000이 최대 값으로 입력될 수 있습니다.

 

또한 실수의 경우 소수점 첫째 자리까지 주어지므로 소수점 이하 10,000자리 까지 나올 수 있다는 것을 의미합니다.

 

java의 double형 타입은 소수 부분 15자리까지 오차 없이 표현할 수 있습니다.

 

하여 이번 문제에서는 기본형인 float이나 double이 아닌 BigDecimal이라는 Class를 이용하여 계산을 하고자 합니다.

 

BigDecimal의 경우 연산이나 max, min 비교와 같은 함수 사용이 일반적인 double, float과 달라 사용법을 먼저 보고 오시면 조금 더 쉽게 접근할 수 있을 것 같습니다.

 

먼저 N이 1이고 실수로 1.5가 입력으로 들어온 경우 최대 부분 곱의 값은 1.5가 됩니다.

 

이 말은 DP[1]은 항상 처음 들어온 값이 된다는 것입니다.

 

자 그럼 DP[2]의 값을 구하려면 어떻게 해야 될까요?

 

연속되는 부분이므로 처음 들어온 1.5와 2번째 들어온 값과의 곱이 연속되는 최대의 곱이 될 수도 있고 곱하지 않은 2번째 값이 연속되는 최대의 곱이 될 수도 있습니다.

 

즉 DP[2]의 값은 DP[1] * 2번째 실수 값과 2번째 실수 값 중 큰 값이 되는 것입니다.

 

이 것을 점화식으로 만들어 보면 DP[N] = Max(DP[N-1] * 입력된 N번째 실수, 입력된 N번째 실수)가 됩니다.

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int numCnt = Integer.parseInt(br.readLine());

BigDecimal[] dp = new BigDecimal[numCnt+1];
Arrays.fill(dp, BigDecimal.ZERO);

dp[1] = BigDecimal.valueOf(Double.parseDouble(br.readLine()));

for(int i=2; i<=numCnt; i++) {
	BigDecimal num = BigDecimal.valueOf(Double.parseDouble(br.readLine()));
	dp[i] = dp[i-1].multiply(num).max(num);
}

Arrays.sort(dp);

bw.write(dp[numCnt].setScale(3, RoundingMode.HALF_EVEN) + "\n");
bw.flush();