[SWEA] 수영장

[1952] 수영장

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq

• 김프로는 지출이 너무 많아 1년 동안 각 달의 이용 계획을 수립하고 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 있다.
• 이용권 종류
• 1. 1일 이용권 : 1일 이용가능
• 2. 1달 이용권 : 1달 이용 가능
• 3. 3달 이용권 : 3달 동안 이용 가능
• 4. 1년 이용 가능
• 이용 계획에 따라 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 비용을 출력하는 문제 

 

 

Solution

• permutation()을 사용하는 문제로 알고 풀었는데 풀이 방법이 떠오르지 않아 dp로 풀었다.
• 평소에 dp 문제 어려워했었는데 이번에는 직접 풀어서 기분이 좋았다 ㅎㅎ.
• input : [tc] [이용권 가격] [월별 이용 계획] 

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int[] price;
    static int[] plan;
    static int[] d;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int tc = stoi(br.readLine());
        int count = 0;
        while (tc-- > 0) {
            price = new int[4];
            plan = new int[13];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 4; i++) {
                price[i] = stoi(st.nextToken());
            }
 
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= 12; i++) {
                plan[i] = stoi(st.nextToken());
            }
 
            d = new int[13];
            for (int i = 1; i <= 12; i++) {
                d[i] = Math.min(plan[i] * price[0], price[1]) + d[i - 1];
                if (i >= 3) {
                    d[i] = Math.min(d[i], price[2] + d[i - 3]);
                }
            }
            count++;
            int answer = Math.min(d[12], price[3]); // 최소비용 vs 1년권 비용
            System.out.println("#"+count + " " + answer);
        }
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}