DP 문제
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
연속으로 놓여있는 3잔의 경우 마실 수 없다를 점화식에 적용하는 것을 중점으로 고민하였다.
입력
첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
1,000 * 10,000 = 10,000,000 -> int 형으로 해결 가능
n의 범위
1 ≤ n ≤ 10,000 이었기 때문에, n이 어떤 숫자이든 연속된 3잔이란 조건을 만족할 수 있는 방법이 필요하다고 생각함
case 1
n = 3 일때, [1, 2], [1, 3], [2, 3]을 선택하는 경우의 수가 필요하다.
6, 10, 13, 9, 8, 1 에서 3까지 최대로 마실 수 있는 경우의 수는 [2, 3]을 선택했을 때 !
여기서 DP[n-1], DP[n-2] + N[n]을 통해 [1, 2], [1, 3]에 대한 선택의 경우의 수는 고민할 수 있었지만, [2, 3]을 어떻게 구해야하나? 라는 고민이 있었음.
case 2
n = 4 일 때 DP[1], DP[2] 는 이미 쉽게 구할 수 있었다.
- DP[1] = N[1]
- DP[2] = DP[1] + N[2]
n = 4 일 때는 앞에 1을 선택했을 때와 안했을 때의 차이를 고민할 수 있었다.
- 현재 포도주를 선택 O : [1, 2, 4], [1, 3, 4]
- 현재 포도주를 선택 X : [1, 2], [1, 3], [2, 3]
점화식 도출
-
여기서,
DP[n-1]의 값이 연속된 2자리일 경우 현재 N[n]을 선택할 수 없다. -
만일 DP[n-1]이 DP[n-2] + N[n-1]일 경우(N[n-2]가 선택된), N[n]은 선택할 수 없다.
그러므로,DP[n-2] + N[n]의 형태를 만들 수 있음. -
마지막으로, N[n-1]과 N[n]을 더하되, N[n-2]를 포함하지 않는 점화식 기준을 정할 수 있도록,
N[n-1] + N[n] + DP[n-3]을 통해 N[n-2]가 포함되지 않은 값을 비교할 수 있다.
따라서,
DP[n-1]: 현재 포도주를 마신 양의 수의 합이, 앞의 연속된 포도주를 마셨을 때 보다 작은 경우DP[n-2] + N[n]: 현재 포도주를 마시고, N[n-1] 포도주를 마시지 않았을 때의 경우DP[n-3] + N[n-1] + N[n]: N[n-2] 포도주를 마시지 않고, 현재와 바로 앞 포도주를 마시는 경우
위 기준을 통해서 코드를 구현하여 정답을 도출할 수 있었다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
// 1 ~ n 기준의 index를 맞추기 위해 n+1
int[] grapeDrinks = new int[n+1];
for(int i = 1; i<=n; i++){
st = new StringTokenizer(br.readLine());
grapeDrinks[i]= Integer.parseInt(st.nextToken());
}
int[] dp = new int[n+1];
dp[1] = grapeDrinks[1];
// n == 1일 경우 N[1]만 도출하면 됨.
if(n == 1){
System.out.println(dp[1]);
return;
}
// n >= 2 일 경우 N[1], N[0]을 통해서 비교 가능
dp[2] = dp[1] + grapeDrinks[2];
for(int i = 3; i<= n; i++){
// a1: 현재 포도주를 선택하지 않고, 다음 포도주를 선택할 가능성을 둠.
int a1 = dp[i-1];
// a2: 현재 포도주를 선택하고, 바로 앞 포도주를 선택하지 않음.
int a2 = dp[i-2] + grapeDrinks[i];
// a3: 현재 포도주와 바로 앞 포도주를 선택하지않고, 앞앞 포도주를 선택하지 않음.
int a3 = grapeDrinks[i] + grapeDrinks[i-1] + dp[i-3];
dp[i] = Math.max(a1, a2);
dp[i] = Math.max(dp[i], a3);
}
System.out.println(dp[n]);
//System.out.println(Arrays.toString(grapeDrinks));
//System.out.println(Arrays.toString(dp));
}
}결과
시간복잡도 : O(n)
