백준 2670 자바 - 연속부분최대곱 (BOJ 2670 JAVA)

문제 : boj2670

 

 

1.

  모든 경우를 보면서, 이전 값이 1.0 보다 크다면 현재 입력받은 수를 곱해준다. 이전까지 구해둔 값이 1.0 이하라면 현재값을 곱하는 것이 손해이므로, 현재값부터 다시 연속된 수를 파악하면 된다.

예를들어 1.2 0.9 1.5 가 있고 현재 1.5를 살펴볼 차례라고 해보자. 이전까지의 값의 곱인 1.2*0.9는 1.08이므로 1.0보다 크다. 따라서 1.5까지 곱해서 1.620이 답이 된다. 반면에 1.1 0.9 1.5라면 1.1*0.9 = 0.99 이므로 1.5에 곱하면 오히려 손해이다. 따라서 1.5부터 다시 구해나가는 것이 더 이득이다.

 

  정리하면 현재 입력받은 수가 cur, 이전까지 계산하던 값이 bf 라고 해보자. bf>1.0이라면 bf = bf * cur이 될 것이다. bf<1.0 이라면 bf = cur로 두고 다음 수로 넘어가면 된다. bf=1.0일 경우는 어떻게 하던 똑같다.

 

 

2.

  이 문제의 경우 현재는 double로 풀어도 통과가 된다. 하지만 문제 조건에 따른 최대 결과값은 9.9^10000으로 double형으로 해도 정수부 표현이 불가능한 엄청나게 큰 수이다. 따라서 자바의 경우엔 BigDecimal로 연산을 진행하면 된다. 

 

글 읽기 - 데이터를 추가해주세요.

일단 9.9가 10000개 들어가는 TC를 추가요청하는 글을 써두긴 했는데, 몇몇 코드들을 봤는데 전부 double로 처리되어 있었다. 저거 추가되면 90%이상은 터질 것 같다 ㅋㅋ. 애초에 문제 출제 의도가 큰 수 연산을 의도한 것 같진 않아서, '지문에 결과값이 double로 표현 가능한 값이다.' 정도만 추가되도 좋을 것 같다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()) - 1;
        BigDecimal bf = new BigDecimal(br.readLine());
        BigDecimal max = bf;
        while (n-->0) {
            BigDecimal cur = new BigDecimal(br.readLine());
            if (bf.compareTo(BigDecimal.ONE) > 0)
                bf = bf.multiply(cur);
            else
                bf = cur;

            if (max.compareTo(bf) < 0)
                max = bf;
        }
        System.out.println(max.setScale(3, BigDecimal.ROUND_HALF_UP).toString());
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}