[java] 백준 알고리즘 2156번 포도주 시식 풀이

다이나믹 프로그래밍 문제다.

조건 1이야 마시고 그냥 놔두면 된다라서 알고리즘에서는 별 상관이 없는 것 같고,

조건 2를 만족시키는 것이 중요하다.

앞으로 사용할 변수 명에 대한 설명은 다음과 같다.

quantityWine: 각각 포도주 잔의 양

sumQuantityWine: 해당 순서에서 포도주를 마실 수 있는 최대양

연속 3잔을 마실 수 없다는 말은

(4잔 이상 놓여있다는 전제 하에)

1. 두 칸 전까지의 포도주를 마실 수 있는 최대양 + 현재의 포도주 잔 마시기

   식: sumQauntityWine[현재-2] + qantityWine[현재]

2. 한 칸 전 포도주를 마시고 싶다면 중복을 피하기 위해 

   현재의 포도주 잔 위치에서 3칸 전까지의 포도주를 마실 수 있는 최대양

   식: sumQauntityWine[현재-3] + qantityWine[현재-1] + qantityWine[현재] 

3. 아니면 현재의 포도주잔을 먹지 않고 건너뛰었을 때(현재의 전과 전전잔에서 2잔을 먹은게 더 클 수도 있지 않은가)

   (가장 놓치기 쉬운 부분이라 생각한다. 나도 다른 분들 풀이를 보고 이 조건을 알았다.)

   식: sumQauntityWine[현재-1]

조건 3의 좋은 예시는 (100, 400, 2, 1, 4, 200)의 경우다.

조건 1,2만 만족한다면 답은 701이 나올 것이다.

조건3까지 추가한다면 704가 된다. 예시의 3번째 와인잔인 '2'의 경우 자신을 건너뛰는 것이

500이라는 더 큰 숫자가 나온다. 

조건 3가지 중 가장 큰 값이 현재 순서까지 마실 수 있는 포도주의 최대양이다.

for(int j=3; j<sumQuantityWine.length; j++) {
    sumQuantityWine[j] = Math.max(quantityWine[j] + sumQuantityWine[j-2], quantityWine[j] + quantityWine[j-1] + sumQuantityWine[j-3]);
    sumQuantityWine[j] = Math.max(sumQuantityWine[j], sumQuantityWine[j-1]);
}

위와 같이 식이 만들어진다.

3잔 이하일 경우의 예외처리는 소스를 참고하면 될 것 같다.

* 풀이 소스 

 
public class Baekjoon2156 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int wineGlassesCount = Integer.parseInt(st.nextToken());
        int[] quantityWine = new int[wineGlassesCount]; 
 
        for(int i=0; i<wineGlassesCount; i++) {
            st = new StringTokenizer(br.readLine());
            quantityWine[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] sumQuantityWine = new int[wineGlassesCount];
        sumQuantityWine[0] = quantityWine[0];
 
        if(wineGlassesCount > 2) {
 
            sumQuantityWine[1] = quantityWine[0] + quantityWine[1];
            sumQuantityWine[2] = Math.max(sumQuantityWine[1], Math.max(quantityWine[0]+quantityWine[2], quantityWine[1]+quantityWine[2])); // 잔이 3잔일 경우
 
            for(int j=3; j<sumQuantityWine.length; j++) {
 
                sumQuantityWine[j] = Math.max(quantityWine[j] + sumQuantityWine[j-2], quantityWine[j] + quantityWine[j-1] + sumQuantityWine[j-3]);
                sumQuantityWine[j] = Math.max(sumQuantityWine[j], sumQuantityWine[j-1]);
 
            }
            bw.write(String.valueOf(sumQuantityWine[wineGlassesCount-1]));
 
        }else if(wineGlassesCount == 2){ // 잔이 2잔일 경우
            bw.write(String.valueOf(quantityWine[0] + quantityWine[1]));
        }else if(wineGlassesCount == 1){ // 잔이 1잔일 경우
            bw.write(String.valueOf(quantityWine[0]));
        }
        bw.flush();
    }    
 
}