boj)2156 - 포도주 시식
2020. 9. 19. 16:25ㆍPS/boj
import java.io.*;
import java.util.StringTokenizer;
public class boj_2156 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static long[] dp;
static int[] val;
static int n;
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
dp = new long[n+1];
val = new int[n+1];
for (int i = 1; i <= n; i++) {
val[i] = Integer.parseInt(br.readLine());
}
dp[1] = val[1];
if (n >= 2) {
dp[2] = val[1] + val[2];
}
for (int i = 3; i <= n; i++) {
dp[i] = Math.max(Math.max(dp[i-1], dp[i-2] + val[i]), dp[i-3] + val[i-1] + val[i]);
}
long ans = dp[1];
for (int i = 2; i <= n; i++) {
ans = Math.max(ans, dp[i]);
}
System.out.println(ans);
}
}
- 연속해서 3번 마시면 안되는 조건을 어떻게 처리할건가 ?
- 현재 내가 몇번째 연속해서 마시는지 체크 -> 0, 1, 2 가 가능
- dp[i] = i번째까지 포도주를 마셧을때의 최대값
=> 0 : i번째를 마시지 않았을 경우, 1 : i번째 마시는게 1번 연속인 경우, 2 : i번째 마시는게 2번 연속인 경우
- dp[i] = max( dp[0번연속, 1번연속, 2번연속] );
- 정답은 최댓값을 찾는거니까 dp 배열에서 최댓값 출력
'PS > boj' 카테고리의 다른 글
boj)11055 - 가장 큰 증가 부분 수열 (0) | 2020.09.19 |
---|---|
boj)1932 - 정수 삼각형 (0) | 2020.09.19 |
boj)9465 - 스티커 (0) | 2020.09.19 |
boj)11057 - 오르막수 (0) | 2020.09.19 |
boj)1309 - 동물원 (0) | 2020.09.19 |