백준 2156 - 포도주 시식 ( JAVA )

출처 - 백준 프로그램

---

시간초과 - 부분집합 

import java.io.*;
import java.util.*;
 
public class Main_시간초과 {
    public static int[] drink; //포도주 마셨으면 1 
    private static int n;
    private static ArrayList<Integer> grape;
    private static int max; // 최댓값 
    
    public static void main(String[] args) throws Exception{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine()) ; // 포도주 잔의 갯수 
        drink = new int[n];
        grape= new ArrayList<Integer>();
        for(int i=0; i<n; i++) {
            grape.add(Integer.parseInt(br.readLine())); 
        }
        // 6 10 13 9 8 1
        
        max=0; 
        // grape 리스트 원소 차례대로 시작해서 더해보기 
        for(int i=0; i<n; i++) {
            getMax(i, 0); 
        }
        
        System.out.println(max);
    }// end of main 
 
    private static void getMax(int from, int link) { // from:마실 포도주 , link:연속으로 마신 포도주 갯수 
        if(link==2) {
            from+=1; 
            link=0; 
        }
        if(from >= n) { 
            int count=0; 
            for(int i=0; i<n; i++) { 
                if(drink[i] ==1 ) {
                    count += grape.get(i); 
                }
            }
            if(max < count) max = count; 
            return ;
        }//이번꺼 먹을거면 , 
        drink[from] = 1; 
        getMax(from+1, link+1); 
 
        //안먹을거면 
        drink[from]= 0; 
        getMax(from+1, 0); 
        
 
    }
}// end of class 
 

→ 가능한 모든 경우의 수를 구했다 .

부분집합으로 구했고, 3개 연속으로 되지 않게 하기 위해 link 변수를 사용해 link 가 2가 되면 해당 포도주는 아예 먹지 못하도록 처리하였다 .

먹은 포도주는 drink 배열의 값을 1로 해서, 마지막에 값이 1인 포도주의 값을 더해주었다. 

예제 답은 잘 나왔지만 시간초과가 났다 !! 

 

 

런타임에러 - dp 

import java.io.*;
import java.util.*;
 
public class Main_런타임에러 {
 
    public static void main(String[] args) throws Exception{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine()) ; // 포도주 잔의 갯수 
        int[] grape= new int[n]; //포도주 양 
        int[] dp = new int[n]; //각 위치까지의 포도주 최댓값 저장 
        
        for(int i=0; i<n; i++) {
            grape[i] = Integer.parseInt(br.readLine());
        }
        // [0] [1] [2] [3] [4] [5]
        //  6   10  13  9   8   1
        
        // 두잔까지는 다 먹는게 최댓값 
        dp[0] = grape[0]; 
        dp[1] = grape[0]+grape[1]; 
        //세잔째에는, xoo 에서 dp[n-3] 인덱스가 음수됨 -> 따로 정의해주기
        //               oox                oxo               xoo  
        dp[2] = Math.max(dp[1], Math.max(dp[0]+grape[2], grape[1]+grape[2]));
        
        for(int i=3; i<n; i++) {
            //                   oox                   oxo                    xoo 
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+grape[i], dp[i-3]+grape[i-1]+grape[i]));
        }
        
        System.out.println(dp[n-1]);
    
        
    }// end of main 
}// end of class 
 

→ dp 를 이용해서 풀었다.

각 지점까지의 최댓값을 구해서 dp 배열에 저장

1잔, 2잔까지는 포도주를 모두 마시는 것이 최댓값이기 때문에 dp[0] 과 dp[1] 은 따로 구해주었고, 

이후부터는 3잔연속 안마시고, 최대한 많이 마시는 것을 찾아야한다. 

 

이번에 마실 포도주가 i 번째 라고 할 때, 

• oox ( 이전까지는 모두 마시고, 이번에는 안마심 ) = dp[i-1] 
• oxo ( 이이전(?) 에는 마셨고, 바로 이전에는 안마셨고,  이번에 마심 ) =  dp[i-2] + grape[i]
• xoo ( 이이전에는 안마셨고, 바로 이전에 마셨고, 이번에도 마심 ) = grape[i-3] + grape[i-1] + grape[i] 

근데 !! 런타임에러가 발생했다.

포도주는 1개 이상이 주어진다. 만약 포도주가 하나만 있을 때, dp[1] 이후부터는 존재할 수가 없다. 

그렇기 때문에 런타임 에러 발생 . 

 

 

최종코드 - dp 

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws Exception{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine()) ; // 포도주 잔의 갯수 
        int[] grape= new int[n]; //포도주 양 
        int[] dp = new int[n]; //각 위치까지의 포도주 최댓값 저장 
        
        for(int i=0; i<n; i++) {
            grape[i] = Integer.parseInt(br.readLine());
        }
        // [0] [1] [2] [3] [4] [5]
        //  6   10  13  9   8   1
        
        // 한잔은 무조건 먹는게 최댓값 
        dp[0] = grape[0];     
    
        for(int i=1; i<n; i++) {
            if(i==1) {
                dp[1] = grape[0]+grape[1]; 
                continue ; // 밑에 코드 안가게 
            }
            if(i==2) {
                dp[2] = Math.max(dp[1], Math.max(dp[0]+grape[2], grape[1]+grape[2]));
                continue ;
            }
            //                   oox                   oxo                    xoo 
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+grape[i], dp[i-3]+grape[i-1]+grape[i]));
        }
        
        System.out.println(dp[n-1]);
    
        
    }// end of main 
}// end of class 
 

→ 위의 런타임 에러를 방지 하기위해, 1잔 일때의 dp[0] 만 정의를 해두었다. (무조건 발생 ) 

이후부터는 반복문을 돌면서 , dp[1] 과, dp[2] 는 따로 조건을 걸어주었다.

• dp[1] = 두잔 : 무조건 두잔 다 마셔야 최댓값 
• dp[2] = 세잔 : 3잔일 때는, xoo 에서 dp[i-3] 이 dp[-1] 로 존재 할 수 없기 때문에, grape[1] + grape[2] 로 따로 정의 
• dp[3] ~ = oox /oxo / xoo 중 최댓값 구하기 

※ i 가 1 일때와 2일 때는 if 문안의 코드만 실행 해야 하기때문에, continue 를 추가 해주었다.