[백준] 2156

ZEDY·2024년 8월 5일

[코딩테스트] 알고리즘 문제풀이

목록 보기

37/46

백준 2156번 문제는 DP를 이용하여 해결하는 와인잔 문제입니다. 이 문제의 목표는 연속된 세 잔을 마실 수 없다는 조건 하에 최대한 많은 와인을 마시는 방법을 찾는 것입니다. 제 코드를 통해 이 문제를 해결하는 방법을 설명하겠습니다.

문제 이해 및 접근 방식

우선 문제를 이해하기 위해서는 몇 가지 예제와 규칙을 이해해야 합니다.

연속된 세 잔의 와인은 마실 수 없다.
각 잔의 와인 양이 주어졌을 때, 최대로 마실 수 있는 와인의 양을 계산해야 한다.

예제를 통해 쉽게 이해할 수 있습니다.

예제

와인의 양이 다음과 같다고 가정해봅시다: [15, 1, 10, 14, 15, 9]

이를 토대로 가능한 최대 와인 섭취량을 계산해보겠습니다.

코드 설명

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P2156 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] number = new int[n];

        for(int i = 0; i < n; i++){
            number[i] = Integer.parseInt(br.readLine());
        }

        int case0 = 0; // 이번 잔 O -> 지난 잔 X -> 지지난 잔 O
        int case1 = 0; // 이번 잔 O -> 지난 잔 O -> 지지난 잔 X
        int case2 = 0; // 이번 잔 X -> 지난 잔 O

        int temp0 = 0;
        int temp1 = 0;
        int temp2 = 0;

        for(int i = 0; i < n; i++){

            temp0 = case0;
            temp1 = case1;
            temp2 = case2;

            case0 = temp2 + number[i];
            case1 = temp0 + number[i];
            case2 = Math.max(Math.max(temp0, temp1), temp2);
        }

        int answer = Math.max(Math.max(case0, case1), case2);

        System.out.println(answer);
    }
}

상세 설명

위 코드는 아래의 과정을 통해 문제를 해결합니다.

입력 받기:
- BufferedReader를 이용해 와인의 양을 입력받습니다.
- number 배열에 와인의 양을 저장합니다.
초기 변수 설정:
- case0: 현재 잔을 마시고, 지난 잔을 마시지 않고, 지지난 잔을 마시는 경우.
- case1: 현재 잔을 마시고, 지난 잔도 마시고, 지지난 잔을 마시지 않는 경우.
- case2: 현재 잔을 마시지 않고, 지난 잔을 마시는 경우.
반복문을 통한 DP 적용:
- temp0, temp1, temp2를 사용하여 이전의 값을 저장합니다.
- case0: 현재 잔을 마시고, 지지난 잔을 마신 경우를 계산합니다.
- case1: 현재 잔을 마시고, 지난 잔을 마신 경우를 계산합니다.
- case2: 현재 잔을 마시지 않고, 이전의 최대 값을 저장합니다.
최종 결과 출력:
- case0, case1, case2 중 최대 값을 선택하여 출력합니다.