[백준] Silver I. 포도주 시식

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

 

사용 알고리즘

• 다이나믹 프로그래밍

 

풀이

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

/*
    테이블: d[i]: i번째 포도주를 선택했을 때 최대값
    점화식
        * d[i] = d[i-2] + s[i]
        * d[i] = d[i-3] + s[i-1] + s[i]
        * d[i] = d[i-1]
 */
public class Main {
    static int n;
    static int [] s = new int[10002];
    static int [] d = new int[10002];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        for(int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(br.readLine());
        }

        d[1] = s[1];
        d[2] = s[1] + s[2];
        for(int i = 3; i <= n; i++) {
            d[i] = Math.max(Math.max(d[i-1], d[i-2] + s[i]), d[i-3] + s[i-1] + s[i]);
        }
        System.out.println(d[n]);
    }
}

 

회고

 

 

이전에 풀었던 계단 문제와 같이 2차원 배열로 푸는건줄 알았는데, 1차원으로 충분히 풀리는 문제였다. 

6

10

13

9

8

1

 

배열이 이렇게 있을 떄, i = 2일떄 경우의 수를 생각하면

 

1. 현재 마시는 경우 

O

X

O

 

2. 전전과 이전의 포도주를 마셔서 현재 포도주를 마시지 않는 경우

O

O

X

 

3. 이전 포도주와 현재 포도주를 마시는 경우

X

O

O

 

위 케이스들을 테이블로 나타내면,

d[i] = d[i-2] + s[i]

d[i] = d[i-1]

d[i] = d[i-3] + s[i-1] + s[i]

 

마지막 빨간색으로 칠한 부분이 처음에 이해가 잘 가지 않았는데, 이전까지의 합을 더해주어야 하기 떄문에 어찌 보면 당연한 풀이다.

 

그리고, 초기화로

d[1] = s[1]

d[2] = s[1] + s[2] (두번째 방문할 때 최댓값)

위 값들을 설정해주면 된다.