메모리: 16028 KB, 시간: 132 ms
다이나믹 프로그래밍
2024년 9월 10일 14:26:41
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.
풀이
100 | 100 | 0 | 0 | 100 | 100 |
1 | 2 | 3 | 4 | 5 | 6 |
4번에 도달할 수 있는 경우의 수를 찾아보자,
우선 연속으로 세 개를 선택하는 건 불가능하다 !
그러므로 3번을 선택하는 경우와 2번을 선택하는 경우로 나눴을 때
3번을 선택한다면 자동으로 1 -> 3 -> 4의 루트가 만들어진다.
2번을 선택한다면 자동으로 1 -> 2 -> 4의 루트가 만들어진다.
연속으로 세 개를 선택하는 건 불가능 하기때문이다 !
그럼 한 컬럼에 도달할 수 있는 분기는 두 개로 나눠진다.
x = x-1 + x-3 or x = x-2
다만 우리는 누적합을 구해야 하므로
x = x-1 + dp[x-3] + x or x = dp[x-2] + x 로 점화식을 만들 수 있다 !
다만 이렇게 점화식을 끝낸다면 문제가 발생한다.
바로 두 칸을 건너 뛰는 경우의 수를 고려하지 않았기 때문이다
100 | 100 | 0 | 0 | 100 | 100 |
1 | 2 | 3 | 4 | 5 | 6 |
이 예시를 다시 살펴보자
위의 점화식으로 문제를 해결하려 하면 위의 테이블에서 최댓값은 300이 나오게 된다.
왜냐하면, 100->100 -> 0 ->100 또는 100 -> 0 ->100->100 이런 식으로 0 하나를 무조건 포함하기 때문이다.
그렇다 위의 점화식에는 한 칸을 건너 뛰는 식은 포함돼 있지만 두 칸을 건너뛰는 식은 포함돼있지 않다.
연속으로 세 개를 고를 수 없는 것이라는 조건을 다시 한 번 생각해봐야한다.
만약
100 | 100 | 1 | 1 | 1 | 100 | 100 |
이라는 테이블이 있다면 100은 무조건 다 포함시켜야 한다.
그리고 세 개를 연속 선택하지 않기 위해 가운데 1만 선택할 것이다.
이를 통해 연속으로 뛰어 넘을 수 있는 최대 갯수는 2칸이라는 것을 알 수 있다.
그럼 2칸을 뛰어 넘는 조건만 점화식에 추가해주면 된다.
x = x - 4 + x - 1 과 같다.
이를 누적합으로 표현한다면, dp[x] = (dp[x-4] + x-1) + x 와 같다.
그럼 점화식은 다음과 같이 변한다.
x = MAX ((x-4 + x-1) or (x-3 + x-1) or (x-3 + x-2) ) + x
이제 코드로 구현해보자
전체코드
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 dp[] = new int[N+3];
int x[] = new int[N+3];
x[0] = 0;
for(int i = 1 ;i<=N;i++){
x[i] = Integer.parseInt(br.readLine());
}
dp[0] = 0;
dp[1] = x[1];
dp[2] = x[1] + x[2];
dp[3] = Math.max(x[2], x[1]) + x[3];
int max = Math.max(dp[2], dp[3]);
for(int i = 4;i<=N;i++){
dp[i] = Math.max(Math.max(x[i-1] + dp[i-3], dp[i-2]),x[i-1] + dp[i-4]) + x[i];
max = Math.max(max,dp[i]);
}
bw.write(max + "");
bw.flush();
}
}
'백준' 카테고리의 다른 글
백준 10844번 쉬운 계단 수 (java) (0) | 2024.09.12 |
---|---|
백준 15486번 퇴사 2 (java) (0) | 2024.09.11 |
백준 2193번 이친수(java) (0) | 2024.09.09 |
백준 9465번 스티커 (java) (3) | 2024.09.07 |
백준 1912번 연속합(java) (0) | 2024.09.05 |