[백준] 2156 포도주 시식
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
2021-01-03
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main2156 {
public static int N, arr[], dp[];
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine().trim());
N = Integer.parseInt(st.nextToken());
arr = new int[N];
dp = new int[N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(bf.readLine().trim());
arr[i] = Integer.parseInt(st.nextToken());
}
// dp[i-1] : 현재 선택 x, 그 전 선택 o, 그 전전 선택 o
// arr[i] + arr[i-1] + dp[i-3] : 현재 선택 o, 그 전 선택 o, 그 전전 선택 x, 그 전전전 선택 o
// arr[i] + dp[i-2] : 현재 선택 o, 그 전 선택 x, 그 전전 선택 o
if(N >= 1) dp[0] = arr[0];
if(N >= 2) dp[1] = arr[1] + arr[0];
if(N >= 3) dp[2] = Math.max(dp[1], Math.max(arr[2] + arr[1], arr[2] + arr[0])); //i-3때문에 미리처리
for(int i = 3; i < N; i++) {
dp[i] = Math.max(dp[i-1], Math.max(arr[i] + arr[i-1] + dp[i-3], arr[i] + dp[i-2]));
}
System.out.println(dp[N-1]);
}
}
|
cs |
void2017.tistory.com/103?category=819361
[백준] 2579 계단 오르기
www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/proble..
void2017.tistory.com
문제를 봤을 때 계단 오르기와 굉장히 유사하다고 생각을 했었다. 그래서 계단 오르기처럼 풀었는데 계속 답이 맞지 않아 결국 다른 사람의 문제풀이를 찾아봤다.
#문제풀이
'계단 오르기'는 그 전 계단을 밟았냐 안 밟았냐 2개의 케이스로 나눴다면, '포도주 시식'은 주석에 쓴대로 3가지 케이스를 나눠서 생각해야한다.
(1) dp[i-1] : 현재 선택 x, 그 전 선택 o, 그 전전 선택 o
(2) arr[i] + arr[i-1] + dp[i-3] : 현재 선택 o, 그 전 선택 o, 그 전전 선택 x, 그 전전전 선택 o
(3) arr[i] + dp[i-2] : 현재 선택 o, 그 전 선택 x, 그 전전 선택 o
3가지 케이스에서 max 값을 찾으면 된다.