문제 정보
플랫폼 : 백준
분류 : Dynamic Programming (동적 프로그래밍)
난이도 : 실버4
링크 : https://www.acmicpc.net/problem/2670
시간제한 및 메모리 제한 검증
O(n) 풀이 : 시간제한 ok
자료형 : 소수점을 활용하므로 double
풀이
그리디 알고리즘 이후 DP문제를 풀어봤다. 역시 나는 DP에 약하다.. 실버4문제임에도 불구하고, 3번의 실패와 다른 블로그를 참조한 이후(?) 풀 수 있었다... 사실 어제 포스팅을 못한 이유는, 공부를 안해서가 아니라 문제를 못풀어서이다!......... 음. 아무쪼록 DP 유형 연습을 열심히 해야겠다.
알고리즘
1. 입력을 받는다.
2. double max = arr[0];으로 선언한다.
3. for i -> 1 to n까지 반복하면서, arr[i-1]*arr[i]가 arr[i]보다 크다면, arr[i]를 갱신한다.
이전까지 누적 곱 x 현재 값이, 현재 값보다 크다면 갱신하는 것이다.
당연하게도, 누적 곱 x 현재 값이 더 작다면 굳이 갱신하지 않는다.
4. arr[i]가 max값보다 크다면 max를 갱신한다.
5. max를 출력한다.
생각해보면 그렇게 어려운 알고리즘은 아닌데, 이걸 생각해낸다는게 어려울 뿐...
입력데이터가 크지 않아 Scanner로 처리했는데, Double을 받아서 그런지..
Scanner로 받았을 때 796ms
BufferedReader로 받았을 때 192ms가 나왔다.
코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. 입력을 받는다.
int n = Integer.parseInt(br.readLine());
double[] arr = new double[n];
for(int i = 0; i < n; i++) {
arr[i] = stod(br.readLine());
}
// 2. double max = arr[0];으로 선언한다.
double max = arr[0];
// 3. for i -> 1 to n까지 반복하면서,
for(int i = 1; i < n; i++) {
// arr[i-1]*arr[i]가 arr[i]보다 크다면, arr[i]를 갱신한다.
arr[i] = Math.max(arr[i], arr[i-1] * arr[i]);
// 4. arr[i]가 max값보다 크다면 max를 갱신한다.
max = Math.max(max, arr[i]);
}
// 5. max를 출력한다.
System.out.printf("%.3f", max);
}
public static double stod(String str) {return Double.parseDouble(str);}
}
더 많은 정답 코드
블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.
