-
[알고리즘-JAVA] 백준 알고리즘 2156번 - 포도주 시식알고리즘 2019. 8. 15. 16:03
접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?조건에 따라 최대로 마실 수 있는 포도주의 양을 구하는 문제이다.
2. 나의 방식대로 문제를 재정의 하자.d[n][k] = n번째 포도주가 k연속일 경우의 최대값.
3. 어떤 알고리즘과 자료구조를 사용할 것인가?배열, Bottom-up
4. 어떻게 계산할 것인가?
1) 입력Scanner이용
2) 시간 복잡도 계산
O(N) - n번째 배열까지 만들고 탐색
5. 주의할 점은 무엇인가?count가 1일때를 고려하지 않아서 에러가 났다.
6. 풀이 과정
d[n][k] = n번째 포도주잔을 마실 때 연속 k인 경우
d[n][0] = n번째 포도잔이 연속 0번째인 경우 = max(d[n-1][0], d[n-1][1], d[n-1][2]
d[n][1] = n번째 포도잔이 연속 1번째인 경우 = d[n-1][0] + arr[n] (그 전 포도잔은 무조건 마시지 않은 상태)
d[n][2] = n번째 포도잔이 연속 2번째인 경우 = d[n-1][1] + arr[n] (그 전 포도잔은 무조건 마신 상태)
import java.util.Scanner; import java.lang.Math; public class Main { public static int d[][]; public static int arr[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int count = sc.nextInt(); arr = new int[count]; d = new int[count][3]; for (int i = 0; i < count; i++) { int temp = sc.nextInt(); arr[i] = temp; } if (count == 1) { System.out.println(arr[0]); } else { d[0][0] = 0; d[0][1] = arr[0]; d[0][2] = 0; d[1][0] = arr[0]; d[1][1] = arr[1]; d[1][2] = arr[0] + arr[1]; for (int i = 2; i < count; i++) { d[i][0] = Math.max(d[i - 1][0], Math.max(d[i - 1][1], d[i - 1][2])); d[i][1] = d[i - 1][0] + arr[i]; d[i][2] = d[i - 1][1] + arr[i]; } System.out.println(Math.max(d[count - 1][0], Math.max(d[count - 1][1], d[count - 1][2]))); } } }
'알고리즘' 카테고리의 다른 글
[알고리즘-JAVA] 백준 알고리즘 1912번 - 연속합 (0) 2019.08.15 [알고리즘-JAVA] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분수열 (0) 2019.08.15 [알고리즘-JAVA] 머지소트(Merge Sort)구현 (0) 2019.08.11 [알고리즘-JAVA] 백준 알고리즘 1991번 - 트리의 순회[미완] (0) 2019.08.11 [알고리즘-JAVA] 백준 알고리즘 11724번 - 연결 요소의 개수 (0) 2019.08.08