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

문제 2670번 (DP, 브루트포스)

 :  N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아 곱 출력

 

 

 → 최대값 = 1.638

 

[입력]

 :  첫째 줄 양의 실수들의 개수 N ( N  ≤ 10000 자연수)

 :  다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다 ( 소수점 첫째자리까지 /  0.0 ≤ 수 ≤ 9.9 )

 

 

[출력]

 :  최댓값을 소수점 이하 넷째 자리에서 반올림해서 출력

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

 

 [ 코드 1) 브루트포스 ]

import java.io.*;
import java.util.*;
public class Main{
    static int n;
    static double arr[];
    static double result = Double.MIN_VALUE;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new double[n];
        for(int i=0; i<n; i++){
            arr[i] = Double.parseDouble(br.readLine());
        }
        
        brute(0);
        
        System.out.printf("%.3f\n",result);
    }
    
    public static void brute(int start){
        if(start == n)
            return;
        
        double sum = 1.0;
        for(int i= start; i<n; i++){
            sum *= arr[i];
            result = Math.max(result, sum);
        }
        
        brute(start+1);
        
    }
}

 

 

 [해설1]
     

 :  static int n;  
    static double arr[];  정수형이 아닌 실수형 
    static double result = Double.MIN_VALUE;  max값 구해야해서 MIN으로 설정
  

 :  n = Integer.parseInt(br.readLine());  n입력
    arr = new double[n];  실수 배열 초기화
    for(int i=0; i<n; i++){  
            arr[i] = Double.parseDouble(br.readLine());  실수 입력받기
    }
        
 :  brute(0);  브루트포스 실행
        
 :  System.out.printf("%.3f\n",result);  소수점 세번째 자리에서 반올림 
    
    
 :  public static void brute(int start){  start 노드부터 시작해서
        if(start == n)  재귀 종료조건 
            return;  n되면 종료
        
        double sum = 1.0;  곱하면서 증가시킬거라 0이 아닌 1로 초기화
        for(int i= start; i<n; i++){  start부터 n까지 곱셈 반복
            sum *= arr[i];  sum에 arr[i] 곱해서 갱신
            result = Math.max(result, sum);  곱 중에 최대값 구해서 갱신
        }
        
        brute(start+1);  반복문 끝나면 시작노드 +1 해서 브루트포스 재귀
          
    }

[ 코드 2) DP ]

import java.io.*;
import java.util.*;
public class Main{
    static int n;
    static double result = Double.MIN_VALUE;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        double dp[] = new double[n];
        
        double result = Double.MIN_VALUE;
        
        for(int i=1; i<n; i++){
            dp[i] = Double.parseDouble(br.readLine());
            dp[i] = Math.max(dp[i],dp[i]*dp[i-1]);
            result = Math.max(dp[i], result);
        }
        
        System.out.printf("%.3f\n",result);
    }
}

 

 

 

 [해설2]
     

 :  static int n;  
    static double result = Double.MIN_VALUE;  max값 구해야해서 MIN으로 설정
  

 :  n = Integer.parseInt(br.readLine());  n입력
    double dp[] = new double[n];  dp 초기화
         
 :  for(int i=1; i<n; i++){
            dp[i] = Double.parseDouble(br.readLine());  dp에 입력 담기
            dp[i] = Math.max(dp[i],dp[i]*dp[i-1]);  현재 입력값과 이전 입력값과 비교했을 때 큰 값을
            result = Math.max(dp[i], result);
    }
        
 :  System.out.printf("%.3f\n",result);  소수점 세번째 자리에서 반올림 후 출력
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

https://www.acmicpc.net/problem/2670

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *