[알고리즘] 백준 2156 자바 JAVA 동적프로그래밍

 

 

 

먼저.. 인간은 다 비슷한 동물이고 일정 지능이 되면 결국 비슷한 경험을 하게 되는 것 같다. (!!!)

 

이 2156번 문제도 마찬가지다. ㅋㅋㅋㅋ 2579 문제랑 되게 유사하다. 다만 다른 점은 계단 문제는 규칙 안에서 무조건 하나는 밟게 되어 있는 반면, 이 포도주 문제는 그렇지 않다. 이 문제는 선택하지 않을 수 있다. 이게 무슨 말이냐면 ..

 

먼저 3가지 측면이 존재한다.

 

1. 현재 포도주와 직전의 포도주를 마신다.

2. 현재 포도주와 전전 포도주를 마신다.

3. 현재 포도주를 마시지 않고 전의 포도주를 마신 케이스를 선택한다.

 

 

 

그니까 1 2번은 2579 문제에서 풀어서 알겠는데.. 3번은 무슨이야기이냐.

 

예를 들어,

(i=0) 20

(i=1) 50

(i=2) 5     <<< 현재 위치

이렇게 나열 되어 있다고 가정해보자. 

 

현재 2번째 포도주를 마시게 되면 연속하여 3번 마실 수 없기 때문에 20이나 50 중에서 골라야한다. 근데 이 문제는 연속 3번만 아니면 되기 때문에, 꼭 0과 2, 1과 2 이런식으로 선택될 필요가 없다. 0과 1을 선택하고 2를 선택하지 않을 수 있다. 즉, 20 + 5가 아니고 50 + 5도 아니고 그냥 20 + 50으로 최대를 선택하면 되는 것이다. 이렇게 되면 i번째를 선택하는 것이 아니고 규칙에 의하여 그냥  i-1번째를 선택하면 그 안에서의 최대값을 선택하는 꼴이 된다.

 

 

 

public class BaekJoon_16_2156 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());

		int[] arr = new int[10001];
		int[] dp = new int[10001];

		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(reader.readLine());
		}

		dp[1] = arr[1];
		dp[2] = arr[1] + arr[2];
		for (int i = 3; i <= n; i++) {
			int stepTwo = dp[i - 2];
			int stepOne = dp[i - 3] + arr[i - 1];

			dp[i] = Math.max(dp[i - 1], arr[i] + Math.max(stepTwo, stepOne));
		}

		writer.write(dp[n] + "");

		writer.flush();
		reader.close();
		writer.close();
	}

}

 

stepOne stepTwo 안하고 그냥 바로 Math.max 안에 넣어도 된다.