[JAVA] # 2156 포도주 시식

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

2156번: 포도주 시식

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int N;
    static int[][] dp; // 0: 안마심 / 1: 1연속 마심 / 2: 2연속 마심
    static int[] wine;

    public static void print() {
        for(int i = 0; i < N; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println("----");
    }

    public static int func() {
    
        // 초기화
        dp[0][1] = wine[0];
        
        // 메인
        for(int i = 1; i < N; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][0] = Math.max(dp[i][0], dp[i - 1][2]);
            dp[i][1] = dp[i - 1][0] + wine[i];
            dp[i][2] = dp[i - 1][1] + wine[i];
            //print();
        }
        
        // 출력
        int ans = Math.max(dp[N - 1][0], dp[N - 1][1]);
        return Math.max(ans, dp[N - 1][2]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dp = new int[N][3];
        wine = new int[N];
        for(int i = 0; i < N; i++) {
            wine[i] = sc.nextInt();
        }
        System.out.println(func());
    }
}

dp 문제!

 

3번 연속으로 와인을 마실 수는 없기 때문에 dp[N][3] 배열을 이용해서 안마심 / 1연속 마심 / 2연속 마심

의 경우를 구분하여 최댓값을 구할 수 있도록 했다.

 

dp[i][0]의 경우, 두번 연속 이상으로 안 마시는 경우가 올 수도 있기 때문에 [0], [1], [2]중 최댓값을 넣어줘야 한다

 

*반례

6

1000

1000

1

1

1000

1000

 

----

이때 1, 1 구간에서 두번 연속 와인을 마시지 않아야 뒤에 1000, 1000을 둘 다 마실 수 있기 때문에 이 점을 반드시 고려해줘야함.

 

 

크게 어렵지는 않았다!