[java 백준] 실버 1/ 2156번 포도주 시식

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

2156번: 포도주 시식

 

import java.util.Scanner;
 
public class Main {
 
    public static int n;
 
    public static int[] arr;
    public static int[] dp;
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n + 2];
        dp = new int[n + 2];
        int count = 0;
        for (int i = 1; i <= n; i++) {
 
            arr[i] = sc.nextInt();
 
        }
        dp[1] = arr[1];
        dp[2] = arr[2] + arr[1];
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
        }
        System.out.println(dp[n]);
    }
 
}

 

누적한 값을 이용해서 풀어야겠다고 생각이들었다.(당연히 dp니까!)

dp[1]=6

dp[2]=16

dp[3]=23

이런 식으로 진행되고, 점화식을 세워야 겠다고 생각했다.

n이 3이고 6,10,13이 있을 때 최대값은 6,10 -->16 일 수도 있고, 10,13-->23 일수도 있다.

이런 경우 최대값이 23일 수 있게 점화식을 만드는게 중요했다.

 

내가 간과한 것은 Math.max 안에 Math.max가 하나 더 들어갈 수 있던 것이였다!

Math.max가 하나 더 들어간다는 것은 비교대상이 더 늘어났다는 것인데

 

이는 A방법과 B방법끼리의 비교가 늘어났다는 것이다.

그렇기에 이것을 코드로 옮기면

 

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

 

풀면서 틀린 부분 

---

 

dp[i]=Math.max(dp[i-1],dp[i-2]+arr[i]) 까지는 생각해냈지만, 이럴 경우 n이 5일 때는 만족하지만 3,4일 때는 만족을 하지 않았다. 어기서 max가 두번 들어갈 수 있다는 것을 생각하지 못한게 첫번째로 틀린 부분이고,

dp[4]=28 인데 dp[4]=25라 두고 풀어서 규칙을 제대로 구하지 못한게 두번째로 틀린부분이다.

좀더 꼼꼼하게 규칙을 찾아야겠다는 생각이 들었다.