SHARE
TWEET

Untitled

a guest Jun 19th, 2017 40 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package sdk.backjun.dp;
  2.  
  3. import java.util.Scanner;
  4.  
  5. /**
  6.  * 백준, 2156, 포도주 시식
  7.  * 다이나믹 프로그래밍
  8.  *
  9.  * @author whitebeard-k
  10.  *
  11.  */
  12. public class Problem2156 {
  13.     public static void main(String[] args) {
  14.  
  15.         Scanner sc = new Scanner(System.in);
  16.         int n = sc.nextInt();
  17.  
  18.         int[] wine = new int[n + 1];
  19.         for (int i = 1; i <= n; i++)
  20.             wine[i] = sc.nextInt();
  21.         sc.close();
  22.  
  23.         long[][] dp = new long[n + 1][4];
  24.         dp[1][1] = wine[1];
  25.         long maxValue = wine[1];
  26.  
  27.         for (int i = 2; i <= n; i++) {
  28.             dp[i][1] = dp[i - 1][3] + wine[i];  // 한잔을 마시는 경우
  29.             dp[i][2] = dp[i - 1][1] + wine[i];  // 두잔을 연속으로 마시는 경우
  30.             dp[i][3] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][3]);    // 마시지 않는 경우
  31.  
  32.             maxValue = Math.max(Math.max(Math.max(dp[i][1], dp[i][2]), dp[i][3]), maxValue);
  33.         }
  34.  
  35. //      for (int i = 1; i <= 3; i++) {
  36. //          for (int k = 1; k <= n; k++) {
  37. //              System.out.printf("%6d", dp[k][i]);
  38. //          }
  39. //          System.out.println();
  40. //      }
  41.  
  42.         System.out.println(maxValue);
  43.     }          
  44. }
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top