[백준] 2156 포도주 시식

www.acmicpc.net/problem/2156

2156번: 포도주 시식

2021-01-03

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main2156 {
    public static int N, arr[], dp[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        dp = new int[N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine().trim());
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // dp[i-1] : 현재 선택 x, 그 전 선택 o, 그 전전 선택 o
        // arr[i] + arr[i-1] + dp[i-3] : 현재 선택 o, 그 전 선택 o, 그 전전 선택 x, 그 전전전 선택 o
        // arr[i] + dp[i-2] : 현재 선택 o, 그 전 선택 x, 그 전전 선택 o
        if(N >= 1) dp[0] = arr[0];
        if(N >= 2) dp[1] = arr[1] + arr[0];
        if(N >= 3) dp[2] = Math.max(dp[1], Math.max(arr[2] + arr[1], arr[2] + arr[0])); //i-3때문에 미리처리
 
        for(int i = 3; i < N; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(arr[i] + arr[i-1] + dp[i-3], arr[i] + dp[i-2]));
        }
        System.out.println(dp[N-1]); 
    }
}
 

void2017.tistory.com/103?category=819361

[백준] 2579 계단 오르기

문제를 봤을 때 계단 오르기와 굉장히 유사하다고 생각을 했었다. 그래서 계단 오르기처럼 풀었는데 계속 답이 맞지 않아 결국 다른 사람의 문제풀이를 찾아봤다. 

 

#문제풀이

'계단 오르기'는 그 전 계단을 밟았냐 안 밟았냐 2개의 케이스로 나눴다면, '포도주 시식'은 주석에 쓴대로 3가지 케이스를 나눠서 생각해야한다. 

 

(1) dp[i-1] : 현재 선택 x, 그 전 선택 o, 그 전전 선택 o

(2) arr[i] + arr[i-1] + dp[i-3] : 현재 선택 o, 그 전 선택 o, 그 전전 선택 x, 그 전전전 선택 o

 

(3) arr[i] + dp[i-2] : 현재 선택 o, 그 전 선택 x, 그 전전 선택 o

 

3가지 케이스에서 max 값을 찾으면 된다.