[SWEA] 1952 수영장

1. 문제

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

SW Expert Academy

2. 접근방법

1월 ~ 12월 까지

일권으로 쓰는 경우 12

1월 ~ 12월 까지

월권으로 쓰는 경우 12

3개월 씩 끊어서

3개월 10개 

1년

하나

 

경우의 수가 매우 적으니 

찍어보면 경우의 수 18529개가 뜨는데 정확한 계산식은 다음에 추가 할게요

 

바로 브루트 포스 ㄱㄱ하면 풀리는 문제이다.

3. 자바 코드

package algo;

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

public class P1952수영장 {
	static int cost[] = new int[4];
	static int[] year = new int[12];
	static int min = 0;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer 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 = 0; i < 12; i++) {
				year[i] = Integer.parseInt(st.nextToken());
			}
			min = cost[3];
			go(0,0);
			System.out.println("#"+tc+" "+ min);
		}
	}
	static void go(int mon,int price) {
		if(mon>11) {
			min = Math.min(min, price);
			return;
		}
		for(int i = 0 ; i < 3 ; i++ ) {
			if(i == 0) { //일 고르고 가기
				price += year[mon] * cost[i];
				go(mon+1,price);
				price -= year[mon] * cost[i];
			}else if(i == 1) { // 월 고르고 가기
				price += cost[i];
				go(mon+1,price);
				price -= cost[i];
			}else if(i == 2) { // 3개월 고르고 가기
				price += cost[i];
				go(mon+3,price);
				price -= cost[i];
			}
		}
	}
}

4. 마치며

dp 그리디 여러 방법이 있다 더 생각해보자