[백준 알고리즘] (DP) 2156번 Java 풀이

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

알고리즘 문제풀이(PS) 시작하기

 

 

백준 알고리즘 2156번

 

 

hange Nxxxx -> Main && remove package lines!!!

이클립스에서 작성하면서 문제 이름으로 클래스를 생성하여 풀었기 때문에

클래스 이름을 Main으로 바꾸고, package 부분도 지우고 제출해야 정상적으로 돌아갑니다.

 

 

<풀이> - Bottom up

package dp;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class N2156 {
 
    static int dp[];
    static int array[];
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        dp = new int[n];
        array= new int[n];
        for(int i=0; i<n; i++) {
            array[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        
        System.out.println(calculate(n));
    }
    
    public static int calculate(int n) {
        if(n==1) {
            return array[0];
        }else if(n==2) {
            return array[0]+array[1];
        }else {
            dp[0] = array[0];
            dp[1] = dp[0]+array[1];
            dp[2] = Math.max(dp[1], Math.max(array[0]+ array[2], array[1]+array[2]));
            
            for(int i=3; i<n; i++) {
                dp[i] = Math.max(dp[i-3]+array[i]+array[i-1], dp[i-2]+array[i]);
                dp[i] = Math.max(dp[i-1], dp[i]);
            }
            return dp[n-1];
        }
        
    }
 
}
 

 

 

처음 점화식을 세우는 과정에서 스스로 구하지 못해서 다른 분의 풀이를 참고했다.

https://hees-dev.tistory.com/30

[BOJ] 백준 2156 포도주시식-java

 

연속으로 3개를 마시지 못한다고 하는 제약을 3개만 놓고 볼 것이 아니라, 그 이전까지 고려해야한다.

n번째 포도주를 마신다면,

1) n-2번째를 마시지 않고, n-1번째를 마신 경우
-> n-2번째에서 마시지 않았기때문에 n-3번째는 마셔도 되고 안마셔도 된다.
-> 따라서 dp[n] = dp[n-3] + array[n-1] + array[n]

2) n-2번째를 마시고, n-1번째를 마시지 않은 경우
->n-1번째에서 마시지 않았기때문에 n-2번째는 마셔도 되고 안마셔도 된다.
-> 따라서 dp[n] = dp[n-2]+array[n]

두 경우를 비교하여 더 큰 값을 저장하면 된다.

 

이에 더불어 2번 연속으로 포도주를 마시지 않는 경우도 고려해야한다.

dp[n], dp[n-1]을 비교해서 더 큰 값을 저장!!

해주지 않으면 n이 증가한다고해도 dp값이 증가하지 않는 사례가 존재한다.

 

Github: https://github.com/jaeuk9407/AlgorithmBOJ

jaeuk9407/AlgorithmBOJ