Baekjoon/[3] DP

[백준] 2156번 포도주 시식 JAVA (자바) 풀이

Poorm 푸름 2024. 8. 20. 22:56

문제 2156번 (DP)

  

  1. 포도주 잔을 선택하면 모두 마시고 원래 위치에 놓기
  2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다

 :  n개의 포도주 잔이 순서대로 놓여있고 포도주의 양이 주어졌을 때 가장 많은 양을 마셔라

 

 예) 6개의 포도주 / 각각 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때

       첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대이다

 

 

[입력]


 :  첫째 줄에 포도주 잔의 개수 n (1 ≤ n ≤ 10,000)

 :  둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다

    (포도주의 양은 1,000 이하의 음이 아닌 정수)

 

 

[출력]

 

 :   첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력

 


[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)  보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결 작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization) 타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때 모두 계산해야 답이 나올 때
재귀 반복문
시간 복잡도 O(n) 시간 복잡도 O(n)

 

1. dp 규칙 찾기

  • 현재 지점을 기준으로 이전 포도주 연속된 2개를 선택할 경우
    • 현재 지점 = i  /  연속된 2개의 이전 포도주 = dp[i-2]

 

  • 현재 지점을 기준으로 현재를 포함해서 연속된 2개를 선택할 경우 + 3칸 전에 있는 포도주 선택 가능
    • 현재 지점 포함한 연속된 2개의 포도주 = arr[i-1]+arr[i]
    • 3칸 전에 있는 포도주 = dp[i-3]

 

  • 현재 지점과 한칸 떨어져있는 이전 포도주 포함해서 2개 선택 가능
    • 현재 지점 = arr[i]  /  한칸 떨어져 있는 이전 포도주 = dp[i-2]

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N+1];
        for(int i=1;i<=N;i++){
            arr[i]= Integer.parseInt(br.readLine());
        }
        int dp[] = new int[N+1];
        dp[1] = arr[1];
        if(N>1){
            dp[2] = arr[1]+arr[2];
        }
        
        for(int i=3;i<=N;i++){
            dp[i] = Math.max(dp[i-1],Math.max(dp[i-2]+arr[i],dp[i-3]+arr[i-1]+arr[i])); 
        }
        
        System.out.println(dp[N]);
        
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());  N 입력
    int arr[] = new int[N+1];  arr배열
    for(int i=1;i<=N;i++){  입력받기
            arr[i]= Integer.parseInt(br.readLine());
    }

    int dp[] = new int[N+1];  dp배열
    dp[1] = arr[1];  1개 택
    if(N>1){  2개 택
            dp[2] = arr[1]+arr[2];
    }
        
    for(int i=3;i<=N;i++){  dp 식 구현
            dp[i] = Math.max(dp[i-1],Math.max(dp[i-2]+arr[i],dp[i-3]+arr[i-1]+arr[i])); 
    }
        
    System.out.println(dp[N]);  출력
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

https://www.acmicpc.net/problem/2156

 


 

 

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

저작자표시