https://www.acmicpc.net/problem/2156
사용 알고리즘
- 다이나믹 프로그래밍
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
테이블: d[i]: i번째 포도주를 선택했을 때 최대값
점화식
* d[i] = d[i-2] + s[i]
* d[i] = d[i-3] + s[i-1] + s[i]
* d[i] = d[i-1]
*/
public class Main {
static int n;
static int [] s = new int[10002];
static int [] d = new int[10002];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
for(int i = 1; i <= n; i++) {
s[i] = Integer.parseInt(br.readLine());
}
d[1] = s[1];
d[2] = s[1] + s[2];
for(int i = 3; i <= n; i++) {
d[i] = Math.max(Math.max(d[i-1], d[i-2] + s[i]), d[i-3] + s[i-1] + s[i]);
}
System.out.println(d[n]);
}
}
회고
이전에 풀었던 계단 문제와 같이 2차원 배열로 푸는건줄 알았는데, 1차원으로 충분히 풀리는 문제였다.
6 | 10 | 13 | 9 | 8 | 1 |
배열이 이렇게 있을 떄, i = 2일떄 경우의 수를 생각하면
1. 현재 마시는 경우
O | X | O |
2. 전전과 이전의 포도주를 마셔서 현재 포도주를 마시지 않는 경우
O | O | X |
3. 이전 포도주와 현재 포도주를 마시는 경우
X | O | O |
위 케이스들을 테이블로 나타내면,
d[i] = d[i-2] + s[i]
d[i] = d[i-1]
d[i] = d[i-3] + s[i-1] + s[i]
마지막 빨간색으로 칠한 부분이 처음에 이해가 잘 가지 않았는데, 이전까지의 합을 더해주어야 하기 떄문에 어찌 보면 당연한 풀이다.
그리고, 초기화로
d[1] = s[1]
d[2] = s[1] + s[2] (두번째 방문할 때 최댓값)
위 값들을 설정해주면 된다.
'Algorithm > 백준' 카테고리의 다른 글
[백준] Silver I.징검다리 건너기(small) (0) | 2024.06.25 |
---|---|
[백준] Silver I. 쉬운 계단 수 (0) | 2024.06.22 |
[백준] Silver 1. 스티커 (0) | 2024.06.19 |
[백준] Silver II. 가장 큰 증가하는 부분 수열 (0) | 2024.06.17 |
[백준] Silver II. 가장 긴 증가하는 부분 수열 (0) | 2024.06.17 |