[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)2156번, 포도주 시식

문제 링크

2156번: 포도주 시식

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

 

포도주에 대한 규칙은 문제에서 모두 알려주고 있습니다.

알고리즘을 형성하면서 찾게 된 규칙입니다.

1. 포도주는 하나씩 먹으면서 3번 연속은 먹지 않게 2번 건너뛰면서 먹는다.

2. 마지막 포도주는 마시지 않아도 된다.

3. 포도주를 연속으로 안마시고 넘어가도 된다.

 

규칙 1과2는 기본적으로 생각할 수 있는 개념이지만 3번에서는 반례를 찾아보면서 알게되었습니다.

예를 들어 입력값이 10 10 1 1 10 10으로 입력받았다면

10->10->10->10 = 40이 최대값이 됩니다.

여기서 1이 연속되어 있는 구간에 포도주를 마시지 않고 그냥 넘어간 것에서 규칙3을 찾을 수 있었습니다.

코드에서는 재귀할 때

Math.max를 사용하였는데 다음 포도주를 먹는 경우, 연속으로 포도주를 먹지 않고 넘기는 경우, 1칸 뛰어넘고 먹는 경우를 다 확인하여 최대값을 구하도록 하였습니다.

 

포도주 개수와 연속된 3개의 포도주를 마시지 못하기 때문에 확인하기 위한 [포도주의 수+1][3]으로 메모이제이션을 구성하였습니다.

메모이제이션을 -1로 초기화한 이유는 포도주 수가 정수 중 음의 정수가 아닌 정수로 0이 들어갈 수 있기 때문에 -1로 초기화하였습니다.

 

 

• 함수 값 저장할 메모이제이션 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 포도주 시식의 최대수를 얻는 함수 wineTesting을 만들었습니다.
• 포도주에 0이 들어갈 수 있기 때문에 메모이제이션을 -1로 초기화하는 checkInit을 만들었습니다.
• System.out.println을 사용하여 함수 결과를 출력하였습니다.

• -1인 경우 재귀를 반복하여 결과값을 메모이제이션에 저장한 뒤 반환한다.
• check가 -1이 아니면 메모이제이션에 저장된 값이 있기에 그 값을 가져온다.
• 위에 알고리즘 설명을 토대로 재귀하도록 wineTesting함수를 작성하였습니다.

결과 코드

import java.io.*;
public class Main{
	static long[][] check;		//메모이제이션
	static int[] wine;		//포도주 숫자 저장 배열
	static int index;		//포도주 개수
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //-----------입력 저장 및 배열 초기화-----------
    	index = Integer.parseInt(br.readLine());
    	wine = new int[index+1];
    	check = new long[index+1][3];
    	checkInit();
    	for(int i=1;i<=index;i++)
    		wine[i] = Integer.parseInt(br.readLine());
    	System.out.println(wineTasting(0,0));	//결과 출력
    	br.close();
	}
    //-------포도주 시식 최대값 구하는 함수------------
	public static long wineTasting(int depth, int stack) {
		if(depth>index)	//마지막 포도주 넘어갔을 때
			return 0;
		
		if(depth==index)	//마지막 포도주 마셨을 때
			return wine[index];
	
		if(check[depth][stack]==-1) {
			if(stack==2)	//2연속 포도주를 마셨을 때
				check[depth][stack] = wineTasting(depth+2,1) + wine[depth];
			else		//그 이외
				check[depth][stack] = Math.max(wineTasting(depth+1, stack+1)+wine[depth],
						Math.max(wineTasting(depth+2, 1) + wine[depth], wineTasting(depth+1, 1)));
		}

		return check[depth][stack];
		}
     //---------------메모이제이션 배열 초기화 함수--------
	public static void checkInit() {
		for(int i=0;i<=index;i++)
			for(int j=0;j<3;j++)
				check[i][j]=-1;
	}
	}