[Algorithm Study] 백준 2156

SeokHwan An·2022년 7월 16일
0

문제 출처 : https://www.acmicpc.net/problem/2156

문제 정리

  1. 효주는 포도주를 앞에서부터 선택해 마실 수 있다.
  2. 포도주는 한번에 무조건 다 마셔야 한다.
  3. 연속으로 놓여 있는 3잔을 연속으로 마실 수 없다.

이 문제를 해결하기 위해 다이나믹프로그래밍을 이용하였습니다. 포도주가 1잔인 경우 그것이 최대였고 포도주가 2잔인 경우에는 2잔 모두 마시는 것이 최대였습니다. 3잔부터는 다음과 같은 점화식이 생성됩니다.
n >= 3 인 경우 부터
dp[n] = Max(dp[n-1], dp[n-2] + wine[n], dp[n-3] + wine[n-1] + wine[n])

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Math.max;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] wine = new int[n+1];
        for(int i = 1; i <= n; i++){
            wine[i] = Integer.parseInt(br.readLine());
        }
        int[] answer = new int[n+1];
        answer[0] = 0;
        answer[1] = wine[1];
        if(n > 1){
            answer[2] = wine[1] + wine[2];
        }
        for(int i = 3; i <= n; i++){
            answer[i] = max(answer[i-1],max(answer[i-2]+wine[i],answer[i-3]+wine[i-1]+wine[i]));
        }
        System.out.println(answer[n]);
    }
}

0개의 댓글