문제 링크

성능 요약

메모리: 15612 KB, 시간: 128 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 28일 02:29:12

문제 설명

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

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

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

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

입력

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

출력

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

풀이

느낀점

• 계단오르기랑 비슷하다고 생각했는데, 스티커 문제랑 비슷했다.
• 계단오르기는 한번에 한계단 또는 두계단씩만 오를 수 있기 때문에 [i-1], [i-2]만 고려했다.
• 이번 문제는 연속된 세개의 스티커를 선택하는 것만 아니면 모두 가능하지만, 가능하면 선택할 수 있는 포도주의 간격을 좁게해서 많이 선택하는 것이 유리하다.
• 따라서 포도주의 간격이 멀어질 수밖에 없는 상황을 고려해야 한다. (100, 100, 1, 1, 100, 100)
  • 연속된 양많은 포도주 두잔씩을 마셨을때 가운데 너무 적은 포도주가 두잔 연속 있으면 둘 다 건너뛰는 편이 유리하다.

설계 : 10분

• dp테이블을 2차원 배열로 구성하여 dp[포도주 잔 순서][3] 모양으로 둔다.
• 0번: 이전 포도주도 마신 경우, 1번: 2개 앞 포도주를 마신 경우, 2번: 3개 앞 포도주를 마신 경우
  • 0번: 이전 포도주의 이전 포도주는 마신 상태면 안됨. (dp[i-1][1], dp[i-1][2]만 가능)
  • 1번: 2개 앞 포도주는 그 앞에 마신 포도주와 상관없음. (전체 비교하여 최댓값)
  • 2번: 3개 앞 포도주는 그 앞에 마신 포도주와 상관없음. (전체 비교하여 최댓값)

코드(Java)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 포도주 시식_2156
 * Date: 2025.01.28
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		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());

        if (n == 1) bw.write(String.valueOf(wine[1]));
        else {
            int[][] dp = new int[n+1][3];
            dp[1][0] = wine[1];
            dp[2] = new int[] {wine[1] + wine[2], wine[2], 0};

            for (int i = 3; i <= n; i++) {
                int second = Math.max(Math.max(dp[i-2][0], dp[i-2][1]), dp[i-2][2]);
                int third = Math.max(Math.max(dp[i-3][0], dp[i-3][1]), dp[i-3][2]);
                dp[i] = new int[] {Math.max(dp[i-1][1], dp[i-1][2]) + wine[i], second + wine[i], third + wine[i]};
            }

            int answer = 0;
            for (int i = n-1; i <= n; i++) {
                for (int j = 0; j < 3; j++) answer = Math.max(answer, dp[i][j]);
            }
            bw.write(String.valueOf(answer));
        }

		bw.flush();
		bw.close();
		br.close();
	}
}