백준 [자바 java] 백준 2156 : 포도주시식

이 문제는 딱봐도(?) 다이나믹프로그래밍 문제이다. 조금 주의할 점이 있다면 연속으로 세 잔 이상 마실수 없다는 것!

import java.io.*;
import java.util.*;



class Main {
	
	public static void main(String[] arg) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader (System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int arr[] = new int[n+1];
		int[] dp1 = new int[n+1];
		int[] dp2 = new int[n+1];
		
		int i;
		for(i = 1;i<=n;i++) {
			arr[i] = Integer.parseInt( br.readLine());
			
		}
	
		dp1[1] = arr[1];
		int mmax = 0;
		int max = 0;
		int k,l;
		
		
		for(i = 2;i<=n;i++) {
			l =  Math.max(dp2[i-2],dp1[i-2]);
			mmax = Math.max(mmax,l);
			
			dp1[i] = mmax + arr[i];
			dp2[i] = dp1[i-1] + arr[i];
		    k = Math.max(dp1[i], dp2[i]);
		    max = Math.max(max,k);
		}
		if(n ==1) max = arr[1];
		
		System.out.println(max);
}

}

 이 문제는 dp1,dp2로 2개의 배열을 만들어서 풀었다. dp1은 i번째의 포도주가 첫 번째로 먹힐 경우, dp2는 두 번째로 먹힐 경우이다. dp1은 i-2번째와 작거나 같은 포도주의 dp1과 dp2에서 가장 큰 값에 본인의 값을 더한다. 그리고 dp2는 i-1포도주에서 dp1값에다가 본인의 값을 더해서 넣는다. 그리고 최종적으로 나오는 값은 모든 dp1, dp2배열에서 가장 큰 수이다. 

 

실수 1 : dp1에 넣는 과정에서 i-2의 dp1,dp2값만 고려했다. 한마디로 두 번 건너뛰는 경우를 생각하지 않았다. 

 

알아야 할 것: 최대의 값을 구하는 문제에서 두 번 건너뛰는 경우 생각하기 

 

다른 사람 코드와 다른 점: 나와 달리 i번째 포도주를 마시는 경우와 마시지 않는 경우를 나누어 구했다. i와 i-2번째 포도주를 먹는 경우와 i와 i-3, i-1번째 포도주를 먹는 경우 중 큰 값을 저장한 후 dp [i-1]과 비교하여 dp값을 채웠다.

 

 이 코드는 깔끔해서 내가 이제까지 짰던 코드 중에 가장 만족스러운 코드이다. 옛날에는 다른 사람이 짠 dp코드를 와 저런걸 어떻게 해 라는 생각을 했었는데 지금은 나도 할 수 있다!