ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [java] 백준 알고리즘 2156번 포도주 시식 풀이
    알고리즘/백준 알고리즘 2018. 7. 20. 09:44


    다이나믹 프로그래밍 문제다.


    조건 1이야 마시고 그냥 놔두면 된다라서 알고리즘에서는 별 상관이 없는 것 같고,


    조건 2를 만족시키는 것이 중요하다.


    앞으로 사용할 변수 명에 대한 설명은 다음과 같다.


    quantityWine: 각각 포도주 잔의 양


    sumQuantityWine: 해당 순서에서 포도주를 마실 수 있는 최대양


    연속 3잔을 마실 수 없다는 말은


    (4잔 이상 놓여있다는 전제 하에)

    1. 두 칸 전까지의 포도주를 마실 수 있는 최대양 + 현재의 포도주 잔 마시기

       식: sumQauntityWine[현재-2] + qantityWine[현재]


    2. 한 칸 전 포도주를 마시고 싶다면 중복을 피하기 위해 

       현재의 포도주 잔 위치에서 3칸 전까지의 포도주를 마실 수 있는 최대양

       식: sumQauntityWine[현재-3] + qantityWine[현재-1] + qantityWine[현재] 



    3. 아니면 현재의 포도주잔을 먹지 않고 건너뛰었을 때(현재의 전과 전전잔에서 2잔을 먹은게 더 클 수도 있지 않은가)

       (가장 놓치기 쉬운 부분이라 생각한다. 나도 다른 분들 풀이를 보고 이 조건을 알았다.)

       식: sumQauntityWine[현재-1]



    조건 3의 좋은 예시는 (100, 400, 2, 1, 4, 200)의 경우다.


    조건 1,2만 만족한다면 답은 701이 나올 것이다.


    조건3까지 추가한다면 704가 된다. 예시의 3번째 와인잔인 '2'의 경우 자신을 건너뛰는 것이


    500이라는 더 큰 숫자가 나온다. 


    조건 3가지 중 가장 큰 값이 현재 순서까지 마실 수 있는 포도주의 최대양이다.


    1
    2
    3
    4
    for(int j=3; j<sumQuantityWine.length; j++) {
        sumQuantityWine[j] = Math.max(quantityWine[j] + sumQuantityWine[j-2], quantityWine[j] + quantityWine[j-1+ sumQuantityWine[j-3]);
        sumQuantityWine[j] = Math.max(sumQuantityWine[j], sumQuantityWine[j-1]);
    }
    cs


    위와 같이 식이 만들어진다.



    3잔 이하일 경우의 예외처리는 소스를 참고하면 될 것 같다.



    * 풀이 소스 


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
     
    public class Baekjoon2156 {
     
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int wineGlassesCount = Integer.parseInt(st.nextToken());
            int[] quantityWine = new int[wineGlassesCount]; 
     
            for(int i=0; i<wineGlassesCount; i++) {
                st = new StringTokenizer(br.readLine());
                quantityWine[i] = Integer.parseInt(st.nextToken());
            }
            
            int[] sumQuantityWine = new int[wineGlassesCount];
            sumQuantityWine[0= quantityWine[0];
     
            if(wineGlassesCount > 2) {
     
                sumQuantityWine[1= quantityWine[0+ quantityWine[1];
                sumQuantityWine[2= Math.max(sumQuantityWine[1], Math.max(quantityWine[0]+quantityWine[2], quantityWine[1]+quantityWine[2])); // 잔이 3잔일 경우
     
                for(int j=3; j<sumQuantityWine.length; j++) {
     
                    sumQuantityWine[j] = Math.max(quantityWine[j] + sumQuantityWine[j-2], quantityWine[j] + quantityWine[j-1+ sumQuantityWine[j-3]);
                    sumQuantityWine[j] = Math.max(sumQuantityWine[j], sumQuantityWine[j-1]);
     
                }
                bw.write(String.valueOf(sumQuantityWine[wineGlassesCount-1]));
     
            }else if(wineGlassesCount == 2){ // 잔이 2잔일 경우
                bw.write(String.valueOf(quantityWine[0+ quantityWine[1]));
            }else if(wineGlassesCount == 1){ // 잔이 1잔일 경우
                bw.write(String.valueOf(quantityWine[0]));
            }
            bw.flush();
        }    
     
    }
     
     
    cs


    댓글 0

Designed by Tistory.