https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] wine = new int[n+1];
int[] memo = new int[10001];
for(int i=1; i<=n; i++) {
wine[i] = Integer.parseInt(br.readLine());
}
memo[1] = wine[1];
if(n>=2)memo[2] = wine[2]+wine[1];
for(int i=3; i<=n; i++) {
memo[i] = Math.max(memo[i-3]+wine[i-1]+wine[i], Math.max(memo[i-2]+wine[i], memo[i-1]));
}
bw.write(Math.max(memo[n],memo[n-1])+"");
bw.close();
}
}3 이상의 n에서
memo[n] = max(wine[n]+wine[n-1]+memo[n-3] , memo[n-2] + wine[n] , memo[n-1])
3번째 전 잔을 먹고 하나 건너 뛰고 이번잔과 저번 잔을 마신 경우 , 저번 잔을 먹지 않고 이번 잔을 먹는 경우, 이번 잔을 먹지 않는 경우 중 최댓값
'백준' 카테고리의 다른 글
| 백준 동적계획법 - 11054번 : 가장 긴 바이토닉 부분 수열 (1) | 2022.03.05 |
|---|---|
| 백준 동적 계획법 - 11053번 : 가장 긴 증가하는 부분 수열 (1) | 2022.03.05 |
| 백준 동적계획법 - 10844번 : 쉬운 계단 수 (1) | 2022.03.03 |
| 백준 브루트포스 - 18111번 : 마인크래프트 (1) | 2022.03.03 |
| 백준 스택 - 10773번 : 제로 (1) | 2022.03.03 |