1952번 : 수영장 [Java]

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

SW Expert Academy

 

해결방안

DFS 혹은 DP로 풀 수 있는 문제였다. 코드가 더 간단한 것 같아 DP 선택.

 

1월은 (1월 이용계획 * 1일 이용권 가격)과 (1달 이용권 가격) 중 적은 비용을 선택

2월은 (1월까지의 가격 + 2월 이용계획 * 1일 이용권 가격)과 (1월까지의 가격 + 1달 이용권 가격) 중 적은 비용을 선택

3월~12월은 (전 달까지의 가격 + 해당 월 이용계획 * 1일 이용권 가격), (전 달 까지의 가격 + 1달 이용권 가격), (3달 전 까지의 가격 + 3달 이용권 가격) 중 적은 비용을 선택

 

단, 12월은 1년 이용권 가격과도 비교가 필요하다.

 

모든 dp배열을 채운 후 12월에 해당하는 값이 답.

 

 

 

전체 코드

import java.util.Scanner;

public class Solution {
	static int[] price;
	static int[] plan;
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			price = new int[4];
			plan = new int[13];

			for (int i = 0; i < 4; i++)
				price[i] = sc.nextInt();
			for (int i = 1; i < 13; i++)
				plan[i] = sc.nextInt();

			int[] dp = new int[13];

			dp[0] = 0;
			dp[1] = Math.min(plan[1] * price[0], price[1]);
			dp[2] = Math.min(dp[1] + plan[2] * price[0], dp[1] + price[1]);

			for (int i = 3; i <= 12; i++) {
				dp[i] = Math.min(dp[i - 1] + plan[i] * price[0], Math.min(dp[i - 1] + price[1], dp[i - 3] + price[2]));
				if (i == 12) {
					dp[i] = Math.min(dp[i], price[3]);
				}
			}

			System.out.println("#" + tc + " " + dp[12]);
		}
	}
}