Cooper's devlog

포도주 시식:2156번-JAVA 본문

Algorithm/Baekjoon

포도주 시식:2156번-JAVA

cooper_dev 2020. 7. 16. 22:04

1. 문제 링크

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

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

2. 문제 설명

3. 문제 접근

-문제에서 가장 중요한 조건은 '연속으로 놓여 있는 3잔을 모두 마실 수는 없다'는 부분 구현이 핵심이 된다!

1) 해당 칸에 도착 시, 이전 결과를 바탕으로 case 분류하기

(연속 3칸이 되지 못한다는 것은 '연속 2칸 or 한칸만 채우고 있어야 된다'는 의미)

ex) 현시점을 기준으로 이전의 값의 형태 분류

  이전 시점 (현시점)
case1 O O
case2 O X
case3 X O
case4
(최대값을 구하기 때문에 제외!)		 X X

 

2) case에 적용해서 작성하기

-좀 더 큰 경우에서 문제를 접근했을 때의 경우를 구체화한다.

                    이전 현시점
case1   . . . . . . . X O O
case2                   O X
case3                   X O

 

case1: 두칸 채워져 있는 형태, 그 이전은 무조건 X.

case2: 이전 시점만 채워져 있는 형태이므로, 그 이전의 값은 상관X

case3: 현시점만 채워져 있으므로 이전 시점은 무조건 X

 

bottom-up방식으로 접근

  i-4 i-3 i-2 i-1 i
case1   dp[i-3] X arr[i-1] arr[i]
case2       dp[i-1] X
case3     dp[i-2] X arr[i]

3) 점화식을 통해 작성

 

dp[i] = dp[i-3] + arr[i-1] + arr[i]

dp[i] = dp[i-1]

dp[i] = dp[i-2] + arr[i]

 

4. 문제 풀이

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package dp1_practice;
 
import java.util.Scanner;
 
public class Grape_Alcohol {
    static int[] arr;
    static int[] dp;
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        arr = new int[n+1];
        dp = new int[n+1];
        
        for (int i = 1; i <= n; i++)    arr[i] = Integer.parseInt(sc.nextLine());    
        
        dp[1] = arr[1];
        if(n > 1) {
            dp[2] = arr[1] + arr[2];
            for (int i = 3; i <= n; i++)
                dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]));
        }
        
        System.out.println(dp[n]);
        
        sc.close();
    }
}
  

 

<정답 확인>

5. 느낀점 혹은 접근법

1. 처음 접근 시, 이전 시점을 기준으로 case분류를 해서 문제 푸는데 시간 소요가 많이 걸렸다.

'Algorithm > Baekjoon' 카테고리의 다른 글

쉬운 계단 수 : 10844번 - JAVA  (0) 2020.07.17
정수 삼각형: 1932번 - JAVA  (0) 2020.07.16
스티커:9465번 - JAVA  (0) 2020.07.16
RGB거리 : 1149번 - JAVA  (0) 2020.07.16
오르막수:11057번 - JAVA  (0) 2020.07.15
'Algorithm/Baekjoon' Related Articles more
Comments