[SWEA] 수영장 Java 풀이

➊ 문제

김 프로는 1년 동안 수영장을 다니려고 한다.
매달 수영장에 가는 일수는 다음과 같이 하나의 행을 갖는 표 형태로 주어진다.

그리고 김 프로는 4종류의 이용권을 결제할 수 있다.

• 1일 이용권
• 1달 이용권
• 3달 이용권
• 1년 이용권

각 이용권의 요금과 각 달의 이용 계획이 입력으로 주어질 때,
가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고
그 비용을 출력하는 것이 우리의 목표다.

이 문제는 주어진 요금제를 기반으로 수영장을 12개월 동안 이용할 때 최소 비용을 계산하는 문제이다.

➋ 풀이 과정

매달 사용할 요금제를 결정할 때,
각 달마다 최선의 선택을 해야 전체 12개월 동안의 최소 비용을 얻을 수 있다.

현재 달의 최적의 선택이 과거의 선택에 영향을 받는 구조이기 때문에
동적 계획법을 적용하였다!

동적 계획법를 활용하기 위해 먼저 dp 테이블을 생성하였고 모든 값을 0으로 초기화하였다.

아래의 dp 테이블에서 dp[i]는 1월부터 i월까지의 최소 비용을 의미한다!

🚨 이때 IndexError을 방지하기 위해 0월도 생성해주었다.

각 달은 4가지 이용권 중 하나를 선택할 수 있다.

• 1일권 : 이번 달의 수영장 이용 횟수에 따라 1일권을 사용하는 경우
• 1달권 : 이번 달에 1달권을 구매하는 경우
• 3달권 : 이번 달을 포함한 3개월 동안 3달권을 사용하는 경우
• 1년권 : 마지막 12월에 1년권을 사용하는 경우

모든 경우를 고려하고 그 중 가장 적은 요금을 지불하는 경우를 택하자!

① 1일권을 선택할 경우

만약 현재 달을 1일권으로 채운다고 가정한다면
점화식은 아래와 같이 도출할 수 있다.
= 저번 달까지의 요금 + (현재 달 이용 횟수 × 1일권 요금)

dp[i] = dp[i - 1] + (annualPlan[i] * dayFee)

② 1달권을 선택할 경우

만약 현재 달을 1달권으로 결제한다고 가정한다면
점화식은 아래와 같이 도출할 수 있다.

= 저번 달까지의 요금 + (1달권 요금)

dp[i] = dp[i - 1] + monthFee;

③ 3달권을 선택할 경우

만약 현재 달을 3달권으로 결제한다고 가정한다면
3달 전까지의 최적해와 3달권 요금을 합산해야 한다.

= 3달 전까지의 요금 + (3달권 요금)

if (i >= 3) dp[i] = dp[i - 3] + threeMonthsFee;

🚨 여기서 중요한 점은 i가 3 이상일 때만 3달권을 사용할 수 있다는 것이다!

④ 1년권을 선택할 경우

만약 1년권으로 결제한다고 가정한다면
12월까지의 최적해와 1년권 가격을 비교할 수 있다.

if (i == 12) dp[i] = Math.min(dp[i], yearFee);

이처럼 매달마다 1일권, 1달권, 3달권을 비교하여 가장 저렴한 요금제를 선택하고
이를 통해 매달 최소 비용을 갱신한다!

마지막 12월에는 1년권과 기존에 계산된 비용을 비교하여 최종적으로 가장 저렴한 비용을 도출한다.

➌ 전체 코드

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

public class 수영장 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    private static StringBuilder sb = new StringBuilder();

    private static final int TOTAL_MONTHS = 12;

    private static int dayFee;
    private static int monthFee;
    private static int threeMonthsFee;
    private static int yearFee;

    private static int[] annualPlan;
    private static int[] dp;
    private static int minFee;

    private static void solution() {
        for (int i = 1; i <= TOTAL_MONTHS; i++) {
            // 1일권 사용 요금 계산
            dp[i] = dp[i - 1] + annualPlan[i] * dayFee;
            // 1달권 사용 요금 계산
            dp[i] = Math.min(dp[i], dp[i - 1] + monthFee);
            // 3달권 사용 요금 계산
            if (i >= 3) {
                dp[i] = Math.min(dp[i], dp[i - 3] + threeMonthsFee);
            }
            // 1년권 사용 요금 계산
            if (i == 12) {
                dp[i] = Math.min(dp[i], yearFee);
            }
        }

        minFee = dp[TOTAL_MONTHS];
    }

    private static void init() throws IOException {
        tokens = new StringTokenizer(br.readLine());

        dayFee = Integer.parseInt(tokens.nextToken());
        monthFee = Integer.parseInt(tokens.nextToken());
        threeMonthsFee = Integer.parseInt(tokens.nextToken());
        yearFee = Integer.parseInt(tokens.nextToken());

        annualPlan = new int[TOTAL_MONTHS + 1];
        dp = new int[TOTAL_MONTHS + 1];

        tokens = new StringTokenizer(br.readLine());
        for (int i = 1; i <= TOTAL_MONTHS; i++) {
            annualPlan[i] = Integer.parseInt(tokens.nextToken());
        }
    }

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            init();
            solution();
            sb.append("#").append(t).append(" ").append(minFee).append("\n");
        }
        System.out.println(sb);
    }
}