[SWEA] 1952.수영장(dfs, dp).java

#. Problem

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE&&&

* The copyright in this matter is in SWEA

#. Resolution Process

1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it

#. Solve

모든 달에 이용 가능한 이용권을 이용해 보는 완탐으로 해결하였다.

 

최소비용으로 1년 이용권을 저장해둔 후,

1월부터 12월까지

     1일 이용권을 이용할 경우,

     1달 이용권을 이용할 경우,

     3달 이용권을 이용할 경우,

모두 확인해보는 완전탐색이다.

#. Code_dfs

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

public class Solution1952 {

	static int[] cost, plan;
	static int res;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {

			cost = new int[4]; // 1일, 1달, 3달, 1년
			plan = new int[13];
			// 가격 정보
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 4; i++) {
				cost[i] = Integer.parseInt(st.nextToken());
			}
			// 계획 정보
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= 12; i++) {
				plan[i] = Integer.parseInt(st.nextToken());
			}
			// 기본 최소 비용은 1년 이용권
			res = cost[3];
			
			process(1, 0);
			
			System.out.println("#" + tc + " " + res);
		}

	}

	private static void process(int month, int sum) {
		// 이미 최소 비용을 넘어가버리면 cut
		if(res <= sum) return;
		
		if(month > 12) {
			res = Math.min(res, sum);
			return;
		}
		
		// 이번 달에 이용 계획이 없다면
		if(plan[month] == 0) {
			process(month + 1, sum);
		} else {
			// 1일 이용권을 이용할 경유
			process(month + 1, sum + cost[0] * plan[month]);
			
			// 1달 이용권을 이용할 경우
			process(month + 1, sum + cost[1]);
			
			// 3달 이용권을 이용할 경우
			process(month + 3, sum + cost[2]);
		}
	}

}

+

3달 이용권을 이용할 경우를 어떻게 처리할지 살짝 헤맷었는데,

결국 모든 달에 3달 이용권을 구매할 수 있고, 

if(month > 12) 로 12월이 넘어갈 경우를 체크했기 때문에,

3달 이용권을 이용할 때 따로 달 체크를 해줄 필요가 없어졌다.

 

#. Code_DP

plan[i] : i월까지 이용했을 경우의 최소 비용

    1일 : 이전달까지의 최소 비용 + 이용일 * 1일권 금액 

    2일 : 이전달까지의 최소 비용 + 1달권 금액

    3달 : 3달 전까지의 최소 비용 + 3달권 금액

   

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

public class Solution1952 {

	static int[] cost, plan;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {

			// 1일, 1달, 3달, 1년 비용
			cost = new int[4];
			plan = new int[13];
			// 가격 정보
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 4; i++) {
				cost[i] = Integer.parseInt(st.nextToken());
			}
			// 계획 정보
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= 12; i++) {
				int days = Integer.parseInt(st.nextToken());
				// 하루 이용권과 한달 이용권 중 최소 비용을 저장
				plan[i] = Math.min(plan[i - 1] + days * cost[0], plan[i - 1] + cost[1]);
				
				// 3달 이용권을 이용할 경우를 고려
				if(i >= 3) plan[i] = Math.min(plan[i], plan[i - 3] + cost[2]);
			}			

			System.out.println("#" + tc + " " + Math.min(plan[12], cost[3]));
		}

	}
}