[백준,BOJ 2156] 포도주 시식(JAVA 구현,추가풀이)

 

-내 생각

  포도주 시식 문제의 경우 계단 오르기 문제와 유사한 점이 많다고 생각한다. 계단 오르기와의 공통점은 3개의 원소를 연속해서 선택할 수 없다는 점이며, 큰 차이점은 마지막 잔을 반드시 마실 필요가 없다는 것이다. 계단 오르기를 분석하고 이러한 유형의 문제를 풀 때 약간의 요령이 생기긴 했던 건지, 점화식을 첫 번째것은 잘 세웠는데, 두 번째 점화식을 고려하지 못해 오답처리를 받았다가 다른 분들의 도움으로 해결할 수 있었다.

 

-해법

  우선 점화식을 세우기 위해서 적당히 4개 정도의 포도주 잔이 있다고 가정하고 생각해 보았다. 아래가 그 표이다. 우선 특정 포도주를 먹기 위한 경우의 수를 생각해보면, N번 째 포도주를 먹거나 먹지 않거나 이므로 2가지 경우가 발생한다. 이후 만약 먹었을 경우 이전 포도주 역시 먹거나 먹지 않을 수 있다. 이제 N-2번째 포도주의 경우는 고정이 되는데, N과 N-1번째 포도주를 먹었을 때 N-2 포도주는 먹을 수 없다. 왜냐하면 3번 연속으로 마실 수 없기 때문이다. 또한 N-1번째 포도주를 먹지 않았을 경우에는 N-2 포도주를 먹어줘야 한다. 왜냐하면 문제에서 마신 포도주의 최댓값을 구하는 조건이 있으므로, 가능한 경우에는 다 먹는다고 가정하는 것이다. 마지막으로 N-3 번째 포도주의 경우에는 N, N-1을 먹고 N-2를 먹지 않았으므로 N-3을 무조건 먹어준다. 그리고 N, N-2 포도주를 먹고 N-1을 먹지 않은 경우는 N-3 포도주를 먹거나 먹지 않아도 상관이 없다. (이 부분에서 무조건 먹지 않는 이유는 N-3번째 포도주를 N 번 째 포도주라고 생각하면, 이미 나올 수 있는 경우의 수는 모두 구했기 때문에 상관이 없는 것이다.) 마지막으로 N번 째 포도주를 마시지 않은 경우에는 마찬가지로 N-1 번째 포도주를 마시거나 마시지 않을 수 있다. N-2부터는 먹든 안 먹든 결국 N-1 또는 N-2까지 누적된 값이 N에서 마시지 않으므로 d [N] = d [N-1 또는 N-2]가 되므로 이를 정리하면 d [N] = d [N-1]이라 할 수 있다.

 

N-3번 째 포도주	N-2번 째 포도주	N-1번 째 포도주	N번 째 포도주
O	X	O	O
O or X	O	X	O
O or X	O or X	O	X
O or X	O or X	X	X

  즉 최정적인 점화식은 dp [i] =dp [i-1], = dp[i-3] + cost[i-1]+ cost[i], dp[i] = dp [i-2]+cost [i]의 세 가지 경우가 발생하며, 이 중 최댓값을 누적해가면서 저장해주면 문제를 해결할 수 있다. 이를 통해 코드를 작성해 보면,

 

import java.util.*;

public class Main {
	static int n; //N 입력
	static int dp[], cost[]; // 메모이제이션 배열, 비용 배열
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		dp =new int [n+1];
		cost = new int [n+1];
		
		
		for(int i=1;i<=n;i++) { // 비용 입력
			cost[i] = sc.nextInt();
		}
		
        // 최대 i-3까지 고려해 주어야 하므로, dp[1]과 dp[2]는 초기화 해준다.
		dp[1] = cost[1]; 
		if(n>=2) // 이 부분이 존재하지 않으면 N이 1이 입력될 때 런타임 에러가 발생한다.
        		// 2번 배열이 존재하지 않기 때문
			dp[2] = Math.max(dp[1] + cost[2], cost[2]);
            
		for(int i=3;i<=n;i++) { // 3번 포도주 부터 누적해간다.
			if(n>=3)
			dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + cost[i-1]+ cost[i], dp[i-2]+cost[i]));
		}
		
		
		System.out.println(dp[n]);
		
		
	}
	
}

---

 

  이전 풀이를 보면 뭐라 뭐라 길게 설명되어 있는데, 이 문제의 요점은 n번째 와인을 마시는 경우의 수만을 고려하면 된다. 주의해야 할 점은 마지막 잔을 꼭 먹을 필요가 없다는 점에서 계단 오르기 문제와 차이가 존재한다. 즉, n번째 와인을 마시지 않아야 최댓값이 나오는 경우가 분명히 존재하기 때문에 이러한 점만 고려해주면 된다.

N-3번 째 포도주	N-2번 째 포도주	N-1번 째 포도주	N번 째 포도주
O	X	O	O
O or X	O	X	O
O or X	O or X	O	X

  위 두 가지의 행은 계단 오르기와 마찬가지로 n번째 포도주를 마시는 경우의 수이고 마지막 행은 마시지 않는 경우의 수이다. 이 중 최댓값을 찾으면 된다는 의미이다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int a[] = new int[n+1];
		int dp[] = new int[n+1];
		
		for(int i=1;i<=n;i++) {
			a[i] = in.nextInt();
		}
		
		// dp[1] 초기화.
		dp[1] = a[1];
		
		// n이 1인 경우 예외 처리.
		if(n>=2)
			dp[2] = a[1]+a[2];
			
		for(int i=3;i<=n;i++) {
			// 경우의 수 중 최댓값을 취한다.
			dp[i] = Math.max(Math.max(a[i-1]+dp[i-3]+ a[i], dp[i-2]+ a[i]),dp[i-1]) ;
		}
			
		System.out.println(dp[n]);
		
		in.close();
	}

}