📍 문제 설명
💡 접근
n번 까지 포도주를 먹는 방법 중 최대로 마실 수 있는 배열을 사용한다.
3가지의 경우의 수가 있다.
1. 현재 포도주를 먹지 않았을 때는 바로 직전까지의 포도주를 먹을 수 있다.
2. 현재 포도주를 먹었을 때는 직전의 직전까지의 포도주를 먹을 수 있다.
3. 또 다른 경우로는 현재 포도주를 먹고 바로 직전의 포도주를 먹을 수도 있다.
그 중 최댓값을 넣는다.
👩💻 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m, k, min, max, answer = Integer.MAX_VALUE, mod = 10007;
static int[][] board;
static int[] arr, dp, t, p;
static boolean[][] visited;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static ArrayList<String> list = new ArrayList<>();
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
Scanner kb = new Scanner(System.in);
Main T = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = kb.nextInt();
arr = new int[n+1];
//dp[n]은 n번 까지의 포도주를 먹은 방법 중 최댓값
dp = new int[n+1];
for(int i = 1; i <= n; i++) {
arr[i] = kb.nextInt();
}
dp[1] = arr[1];
if(n > 1) dp[2] = arr[1] + arr[2];
//3가지 경우의 수에 대해서 생각한다.
//3번째 부터는 현재 포도주를 먹지 않으면 직전의 포도주까지 먹을 수 있다.
//현재 포도주를 먹으면 직전의 직전 포도주까지만 먹을 수 있다.
//직전의 포도주와 현재의 포도주를 먹는 방법도 있다.
for(int i = 3; i <= n; i++) {
dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]));
}
System.out.println(dp[n]);
}
private void solution() {
}
}
'Algorithm > baekjoon' 카테고리의 다른 글
가장 긴 바이토닉 부분 수열 (0) | 2022.02.16 |
---|---|
가장 큰 증가 부분수열 (0) | 2022.02.16 |
오르막 수 (0) | 2022.02.16 |
동물원 (0) | 2022.02.15 |
RGB거리 (0) | 2022.02.15 |