Q2156. 포도주 시식

먹은 포도주의 value를 저장하며 나아가는 로직

해당 문제를 풀지 못해, 다른 블로그의 글을 봤지만, 이해가 안되는 문제로, 고민 끝에 해결했네요.

함정은 연속된 3개의 포도주는 먹지 못한다는 조건.

따라서 K(i) value에 가능한 값은 k(i-3) or k(i-2) or (k(-1)입니다.

대신 현재 연속으로 먹은 포도주를 파악하기 위해 2차원 배열을 사용합니다.

0번째에는 포도주의 value,

1번째에는 포도주를 연속 한번 먹었을 경우의 value

2번째에는 포도주를 연속 두번 먹었을 경우의 value

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2156 { static long[][] array; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int maxNum = Integer.valueOf(st.nextToken()) + 1; //array[i][0] = 유리잔의 포도주 value //array[i][1] = 연속으로 먹은 포도주 개수가 1개인 경우의 value //array[i][2] = 연속으로 먹은 포도주 개수가 2개인 경우의 value array = new long[10002][3]; for (int i = 2; i <= maxNum; i++) { st = new StringTokenizer(br.readLine()); array[i][0] = Integer.valueOf(st.nextToken()); } array[2][1] = array[2][0]; for (int i = 3; i <= maxNum; i++) { //포도주를 1번 점프했을 경우의 max Value long jump1 = Math.max(array[i-2][2], array[i-2][1]); //포도주를 2번 점프했을 경우의 max Value long jump2 = Math.max(array[i-3][2], array[i-3][1]); //연속 한번의 포도주를 먹었을때의 max Value array[i][1] = Math.max(jump1, jump2) + array[i][0]; //연속으로 먹었을 경우의 value long jump0 = array[i-1][1]; array[i][2] = jump0 + array[i][0]; } long maxValue = 0; for (int i = maxNum-1; i <= maxNum; i++) { for (int j = 0; j <= 2; j++) { if (maxValue < array[i][j]) { maxValue = array[i][j]; } } } System.out.println(maxValue); } }