[백준(Baekjoon)][자바(java)] 2156 : 포도주 시식 / 동적 계획법 1

 

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

2156번: 포도주 시식

 

* 문제

1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하라

 

* 풀이 방법

▶  n개의 포도주 잔이 있고, 시식하는 경우는 3가지임

     i번째 잔을 선택하지 않고 지나가는 경우

     i번째 잔을 선택해서 연속으로 1잔 마신 경우,

     i번째 잔을 선택해서 연속으로 2잔 마신 경우

▶  n*3의 dp배열 생성  ( i : n개의 잔에 각각의 양이 담긴 배열의 인덱스 ) ( j : 시식하는 경우의 수 인덱스 )

▶  현재 잔을 안 마신 경우  ☞  dp[ i ][ 0 ] = Max( dp[ i-1 ][ 0 ], dp[ i-1 ][ 1 ], dp[ i-1 ][ 2 ] )

      현재 잔까지 연속으로 1잔 마신 경우  ☞  dp[ i ][ 1 ] = dp[ i-1 ][ 0 ] + a[ i ];

      현재 잔까지 연속으로 2잔 마신 경우  ☞  dp[ i ][ 2 ] = dp[ i-1 ][ 1 ] + a[ i ];

	6	10	13	9	8	1
x	0	6	16	23	28	33
1	6	10	19	25	31	29
2	(6)	16	23	28	33	32

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), i;
		int a[] = new int[n];
		for( i = 0; i < n; i++ ) 
			a[i] = sc.nextInt();
		sc.close();
		
		int dp[][] = new int[3][n];
		dp[1][0] = a[0];
		for( i = 1; i < n; i++ ) {
			dp[0][i] = Math.max( dp[0][i-1], Math.max( dp[1][i-1], dp[2][i-1] ) );
			dp[1][i] = dp[0][i-1] + a[i];
			dp[2][i] = dp[1][i-1] + a[i];
		}
		
		System.out.println( Math.max( dp[0][n-1], Math.max( dp[1][n-1], dp[2][n-1] ) ) );

	}

}