[백준/2156/Java] 포도주 시식

 

 

문제링크

www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

문제

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

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

 

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

 

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

 

 

풀이

이 문제는 계단 오르기 문제와 유사합니다.

 

2021.04.06 - [Algorithm] - [백준/2579/Java] 계단 오르기

[백준/2579/Java] 계단 오르기

 

가장 많은 양의 포도주를 마셔야 하며, 마시는 규칙은 2가지 입니다.

1. 잔을 선택하면 잔에 들어있는 모든 포도주를 마시는 규칙이므로 마신 포도주의 총합을 구하면 됩니다.

2. 연속을 놓여있는 3잔의 포도주를 마실 수 없습니다.

 

다이나믹 프로그래밍에서 점화식을 구할 때 가장 먼저 쉽게 생각할 수 있는 방법은 N번째에서 규칙을 반대로 생각하면 됩니다.

포도주 잔의 양은 S 배열에 있다고 가정하고 포도주의 총합을 D 배열로 구한다고 가정하겠습니다.

D[N]을 구하는 방법은 2번째 규칙을 이용하면 3가지 경우의 수가 나옵니다.

1. 현재 포도주를 마시지 않습니다. 즉, 연속으로 마신 잔의 수는 0입니다.

2. 현재 포도주를 마시고 연속으로 마신 잔의 수가 1입니다.

3. 현재 포도주를 마시고 연속으로 마신 잔의 수가 2입니다.

연속으로 3잔은 마실 수 없으므로 다른 경우의 수가 없습니다.

 

0번 연속 마심

노란 색으로 표시한 부분이 마신 포도주입니다.

S[N]은 마시지 않았으므로 D[N]에서 가장 높은 양은 D[N-1]입니다.

공식으로 표현하자면 D[N] = D[N-1] + 0 = D[N-1] 이 됩니다.

 

1번 연속 마심

현재 잔 S[N]을 마셨으므로 S[N-1]을 마시지 않은 상태입니다.

따라서, 포도주 총합 D[N]= D[N-2] + S[N]이 됩니다.

 

 

2번 연속 마심

현재 잔과 이전 잔을 마셨으므로 S[N], S[N-1]을 마셨습니다.

그리고 3잔 연속으로 마실 수 없으므로 포도주 총합 D[N] = D[N-3] + S[N-1] + S[N]이 됩니다.

D[N

 

따라서, 포도주 총합은 위 3가지 경우 중 가장 큰 값을 D[N]에 저장하면 됩니다.

D[N] = max(D[N-1], D[N-2]+S[N], D[N-3]+S[N-1]+S[N])

 

 

소스

포도주 잔의 양은 S 배열에 저장하고,  포도주의 총합을 D 배열에 저장하였습니다.

점화식은 JAVA에서 max에 파라미터 3개를 넣을 수 없으므로 Math.max를 2번 감싸면 됩니다.

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

public class Main
{
	static int N;
	static int S[];

	static int Answer;

	static int D[];

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 입력
		N = Integer.valueOf(br.readLine());

		S = new int[N + 1];
		D = new int[N + 1];

		for (int i = 1; i <= N; i++)
		{
			S[i] = Integer.valueOf(br.readLine());
		}

		// 처리
		D[1] = S[1]; // 1잔은 마시는 게 가장 많다.
		Answer = D[1];

		if (N > 1)
		{
			D[2] = S[1] + S[2]; // 2잔은 항상 같이 마시는 게 가장 많다.
			Answer = D[2];
		}

		// 0번 연속 마심 : D[i-1]
		// 1번 연속 마심 : D[i-2] + S[i]
		// 2번 연속 마심 : D[i-3] + S[i-1] + S[i]
		for (int i = 3; i <= N; i++)
		{
			D[i] = Math.max(D[i - 1], Math.max(D[i - 2] + S[i], D[i - 3] + S[i - 1] + S[i]));

//			Answer = Math.max(Answer, D[i]);

			// System.out.println(i + " => " + D[i]);
		}
		
		for (int i = 1; i <= N; i++)
		{
			Answer = Math.max(Answer, D[i]);
		}

		// 출력
		System.out.println(Answer);
	}
}