백준-2156번/포도주 시식 (java)

 

 

이 문제의 핵심은 i-1번째의 포도주를 마시는 경우, i-1번째의 포도주를 마시지 않는 경우, i번째 포도주를 마시지 않는 경우로 나뉜다.

 

1) i-1번째 포도주를 마시지 않는 경우

1	2	3	4
O	O	X	O

 

2)i-1번째 포도주를 마시는 경우

1	2	3	4
O	X	O	O

 

3)i번재 포도주를 마시지 않는 경우

1	2	3
O	O	X

 

이 3가지 경우의 최댓값이 i번째 까지의 최댓값이 된다.

 

이를 바탕으로 점화식을 만들어보면 다음과 같다.

 

Math.max(i번째 포도주 안마시는 경우,Math.max(i-1번째 포도주를 안마시는 경우,i-1번째 포도주를 마시는 경우))

 

정답 코드

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

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		int[] arr = new int[n+1];
		int[] dp = new int[n+1];
		for(int i=1; i<=n; i++) {
			arr[i]=scanner.nextInt();
		}
		
		if(n==1) {
			System.out.println(arr[1]);
			return;
		}
		else if(n==2) {
			System.out.println(arr[1]+arr[2]);
			return;
		}
		dp[1]=arr[1];
		dp[2]=arr[1]+arr[2];
		dp[3]=Math.max(dp[2], Math.max(arr[1]+arr[3],arr[2]+arr[3]));
		
		if(n==3) {
			System.out.println(dp[3]);
			return;
		}
		for(int i=4; i<=n; i++){
				dp[i]=Math.max(dp[i-1],Math.max(dp[i-2]+arr[i],dp[i-3]+arr[i]+arr[i-1]));
		}
		
		
		System.out.println(dp[n]);
		
	}
}

 

느낀점 : 넓은 범위를 바탕으로 점화식을 만들지 말고 좁은 케이스 부터 생각해보면서 점화식을 만들자.