SWEA 1952 수영장(DFS, DP)

SW Expert Academy

수영장을 어떠한 기준으로 끊어야할지 모르기 때문에 모든 경우를 봐줘야한다.

 

DFS의 구조를 트리로 그리면 이해가 쉬워진다.

 

기간은 1년이기 때문에 1년에 해당하는 부분은 상수(final)일 것이고

1일, 1개월,  3개월 단위로 어떤 순서로 할지 모든 경우를 탐색한 다음 비용을 갱신해주면서 답을 찾는다

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

public class Solution{
	static int[] price, data;
	static int res;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int i = 1; i < T+1; i++) {
			price = new int[4];
			data = new int[13];
			
			String[] input = br.readLine().split(" ");
			for (int j = 0; j < 4; j++) {
				price[j] = Integer.parseInt(input[j]);
			}
			
			input = br.readLine().split(" ");
			for (int j = 1; j < 13; j++) {
				data[j] = Integer.parseInt(input[j-1]);
			}
			res = price[3];

			
			dfs(1,0);
			
			System.out.println("#"+i+" "+res);
			
			
			
		}
				
	}
	
	public static void dfs(int depth, int sum) {
		if (depth >= 13) {
			res = Math.min(res, sum);
			return;
		}
		
		if (data[depth] == 0)
			dfs(depth+1,sum);
		else {
			dfs(depth+1, sum + (data[depth] * price[0]));
			dfs(depth+1, sum + price[1]);
			dfs(depth+3, sum + price[2]);
		}
		
		
		
	}
}

 

DP로 푼 풀이

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

public class Solution {
	static int[] price, data, dp;
	static int res;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int i = 1; i < T+1; i++) {
			price = new int[4];
			data = new int[13];
			dp = new int[13];

			String[] input = br.readLine().split(" ");
			for (int j = 0; j < 4; j++) {
				price[j] = Integer.parseInt(input[j]);
			}
			
			input = br.readLine().split(" ");
			for (int j = 1; j < 13; j++) {
				data[j] = Integer.parseInt(input[j-1]);
			}
			res = price[3];
			
			
			
			for (int j = 1; j < 13; j++) {
				int day = data[j] * price[0] + dp[j-1];
				int month_1 = price[1] + dp[j-1];
				dp[j] = Math.min(day, month_1);
				
				if (j>=3) {
					int month_3 = price[2] + dp[j-3];
					dp[j] = Math.min(dp[j], month_3);
				}
			}
			
			System.out.println("#"+i+" "+Math.min(dp[12], price[3]));
			
			
			
		}
				
	}
	

}