2156 포도주 시식

 

 

입력값을 wine 배열에 받는다고 하면,

 

dp[1] = wine[1]

dp[2] = dp[1] + wine[2]

 

이다.

 

그 이후부터는,

 

  dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + wine[i] , dp[i-3] + wine[i-1] + wine[i]))

 

즉, dp[5] 를 구하고 싶으면,

 

1) dp[4]

2) dp[3] + wine[5]

3) dp[2] + wine[4] + wine[5]

 

중에서 제일 큰 값을 고르면 된다. 

 

1) dp[4] 를 구한다는 것은,

연속으로 놓여 있는 3잔을 모두 마실 수 없다고 했으므로,

이미 3,4 번째 포도주를 마셨다는 뜻이 된다. 

그래서 5번째 포도주를 마실 수 없다. 

 

 

2) dp[3] + wine[5] 를 구한다는 것은,

3번째까지 마신 포도주 최대 양에 5번째 포도주의 양을 더한다는 것이다. 

 

 

 

3) dp[2] + wine[4] + wine[5] 를 구한다는 것은,

2번째까지 마신 포도주 최대 양에 4,5 번째 포도주의 양을 더해 마신다는 뜻이다. 

 

 

이렇게 해서 구하면 된다. 

 

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


public class Main {
	
    public static void main(String[] args)  throws IOException {  
    	
    	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
       	  int N = Integer.parseInt(st.nextToken());           	  
       	  int dp[] = new int[10001];
       	  int wine [] = new int[N+1];
       	  
       	  for(int i=1; i<=N; i++) {
       		st = new StringTokenizer(br.readLine(), " ");
       		wine[i] = Integer.parseInt(st.nextToken());      		  
       		  
       	  }
       	 
       	  for(int i =1; i<=N; i++) {      		  
       		  
       		  if(i==1) {
       			  //dp[1] = wine[1]
       			  dp[i] = wine[i];
       			  
       		  }else if(i==2) {
       			  
       			  // dp[2] = dp[1] + wine[2]
       			  dp[i] = dp[i-1]+ wine[i];
       		  }else {     			  
       			  
       			  dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + wine[i] , dp[i-3] + wine[i-1] + wine[i]));
       			  
       		  }
       		  
       	  }
       	  
          System.out.println(dp[N]);
          
    
    }
    
 
     
}

 

 

참고 블로그 : https://codinghentai.tistory.com/46

백준 2156번 포도주 시식 (자바) 풀이