수영장

[문제풀이]

dp테이블의 크기를 12로 생성하여 index를 0부터 11까지로 사용해서 풀어보려고 했지만 1월일때의 dp테이블을 어떻게 갱신해줘야할지 생각이 안나서 테이블 크기를 13으로 하여 index를 0부터 12까지로 정의한 다음 1월일 때 인덱스 에러를 방지하기 위해 0의 index까지 사용했다.

먼저 1일 이용권과 1달 이용권을 사용했을 때의 dp테이블을 먼저 갱신해준 뒤, 3달을 포함할 수 있는 월이면(index가 3이상일 때) 3달 이용권을 사용했을 때의 dp테이블을 1일 이용권, 1달 이용권으로 갱신한 dp테이블과 비교하여 더 작은 값으로 해당 월의 dp테이블을 갱신해준다.

그 후, 맨 마지막 인덱스 dp테이블 값과 1년 이용권 사용할 때의 요금과 비교하여 더 적은 비용이 드는 값을 출력해준다.(1년 이용권과 비교해주는 이유는 1월부터 12월의 이용한 횟수와 관계없이 언제든지 이용이 가능하기 때문이다.)

※ DP방식이 아닌 DFS로도 풀 수 있지만 DP로 푸는것이 더 쉽게 느껴지고 시간복잡도 측면으로도 좋다고 생각해서 DP알고리즘으로 풀었다.

[코드]

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

public class Solution{

	static int[] voucher;
	static int[] year;
	static int[] d;
	//static int min = Integer.MAX_VALUE;	//답
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());	//tc
		
		for(int tc=1; tc<= T; tc++) {
			
			voucher = new int[4];	//4가지 이용권
			year = new int[13];		//1월~12월
			d = new int[13];		//dp테이블 월만큼 생성
			
			Arrays.fill(d, 0);		//dp테이블 0으로 초기화
			
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<4; i++) {
				voucher[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i=1; i<=12; i++) {
				year[i] = Integer.parseInt(st.nextToken());
			}
			
			for(int i=1; i<=12; i++) {
				
				//1일 이용권, 1달 이용권
				d[i] = Math.min(d[i-1]+ year[i]*voucher[0], d[i-1]+voucher[1]);
				
				
				//3달 이용권
				if(i>=3) {
					d[i] = Math.min(d[i], d[i-3]+voucher[2]);
				}
			}
			
			System.out.println("#"+tc+" "+Math.min(d[12], voucher[3]));
		}
		
		
	}

}