포도주 시식 BOJ_2156

앞서 포스팅에 이어서 2차원 DP 방식으로 여러 케이스를 나누어 푸는 방법을 소개하겠습니다.

문제는 다음과 같습니다.

조건은 반드시 확인해서 코드로 정리해야하며 DP 문제는 점화식을 세워야 한다는 것을 잊어선 안됩니다.

※ 조건

1. 포도주 잔 선택 후 마신 다음에는 제자리에 두기 --> 포도주 잔이 자리 위치가 없음 (고정됨)

2. 포도주 잔 선택시 다 마셔야하며 연속 3잔 원샷 X

※ 점화식

D[n] : n번째 순서에서 포도주를 마시는 것

조건에 따라서 연속 3잔을 마실 수 없으므로 총 3가지 케이스가 나오게 됩니다.

[0] --> 술을 마시지 않은 경우

[1] --> 술을 연속 한 잔 마신 경우

[2] --> 술을 연속 두 잔 마신 경우

// 최대로 마실 수 있는 포도주의 양 체크

1. 연속 0잔 마실 경우

D[n][0] = Math.max(D[n-1][0],Math.max(D[n-1][1],D[n-1][2])); 

--> 앞서 n번째일 때 0번 마시고 나머지 n-1번째에서는 안마셔도되고 (연속 0잔) 마셔도됩니다.

(연속 한 잔 --> n-1번째 술을 마신 것 / 연속 두 잔 --> n-1번째 술을 연속 두 번 마신 것)

2. 연속 1잔 마실 경우

D[n][1] = A[n] + D[n-1][0] ; 

--> 연속 한 잔 일 경우 n번째는 술을 마시고 n-1번째는 술을 안먹고 횟수를 체크하면 된다.

3. 연속 2잔 마실 경우

D[n][2] = A[n] + D[n-1][1]; 

--> 연속 두 잔일 경우 n번쨰는 술을 마시고 n-1번째 부터는 술을 마시면서 횟수를 체크하면 된다. 

이는 다음과 같이 바꿀 수 있습니다.

D[n][2] = A[n] + A[n-1] + D[n-2][0]; 

단, 이렇게 할 경우 n의 시작 범위가 달라집니다.

배열이 indexOutOfBoundsError를 피하기 위하여 2부터 시작하도록 설정해야 합니다.

전체 코드는 다음과 같습니다.

---

import java.util.Scanner;

public class 포도주시식 {

private static Scanner scanner;

private static int[][] d;

private static int[] a;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int n = scanner.nextInt(); // 포두주 잔의 개수 n개

// 1부터 n+1번째까지 포도주 양 체크

a = new int[n + 1];

// n은 10000 이하 , 포도주의 양은 1000이하 이기 때문에 충분히 int로 해도 된다.

for (int i = 1; i <= n; i++) {

a[i] = scanner.nextInt(); // 포도주의 양

}

d = new int[n + 1][3]; // 0번 연속 , 1번 연속 , 2번연속

for (int i = 2; i <= n; i++) {

d[i][0] = Math.max(d[i - 1][0], Math.max(d[i - 1][1], d[i - 1][2])); // 연속 x

d[i][1] = d[i - 1][0] + a[i];

d[i][2] = d[i - 2][0] + a[i] + a[i-1];

}

long ans = 0;

ans += Math.max(d[n][0], Math.max(d[n][1], d[n][2]));

System.out.println(ans);

}

}

---

보라색으로 배경색이 된 부분은 다음과 같이 바꿀 수 있습니다.

for (int i = 1; i <= n; i++) {

d[i][0] = Math.max(d[i - 1][0], Math.max(d[i - 1][1], d[i - 1][2])); // 연속 x

d[i][1] = d[i - 1][0] + a[i];

d[i][2] = d[i - 1][1] + a[i];

}

앞서 설명한 대로 코드를 정리한 것이며 이렇게 들어간 값들 중에서 

최대값을 뽑아서 출력해주면 정답이 나오게 됩니다.

감사합니다.