[SWEA] 1952 수영장

문제보기

머리 써보려다가 그냥 재귀로 풀었다. 너무 경우의 수가 많아질 것 같아서 포기해따 … (예: 한달 이용량이 mon1/day 보다 많으면 mon1 선택)

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

public class Main {
  static boolean[] check;
  static int min;
  static int day;
  static int mon1;
  static int mon3;
  static int year;
  static int[] plan;

  static void go(int idx, int sum) {
    // 12월이 넘어가면 종료
    if(idx >= 12) {
      if(sum < min) min = sum; // 최소값 갱신
      return;
    }
    // 이용계획이 없는 날은 건너 뛴다
    if(check[idx] == false) {
      go(idx+1, sum);
      return;
    }
		
    // 1일 이용권을 쓴다 
    go(idx+1, sum + plan[idx]*day);
    // 한달 이용권을 쓴다 
    go(idx+1, sum + mon1);
    // 세달 이용권을 쓴다
    go(idx+3, sum + mon3);


  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    int idx = 1;
    StringBuilder sb = new StringBuilder();
    while(t-->0) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      day = Integer.parseInt(st.nextToken());
      mon1 = Integer.parseInt(st.nextToken());
      mon3 = Integer.parseInt(st.nextToken());
      year = Integer.parseInt(st.nextToken());
      st = new StringTokenizer(br.readLine());
      plan = new int[12];
      check = new boolean[12];

      for(int i = 0 ; i < 12 ; i++) {
        plan[i] = Integer.parseInt(st.nextToken());
        if(plan[i] != 0 ) check[i] = true;
      }

      min = year; // 최소비용의 초기값을 1년권으로 준다
      // 상식적으로 1년권이 가장 비쌀것 같았기 때문(??)
      
      // 1월부터 시작~
      go(0, 0);


      sb.append("#" + idx++ + " " + min + "\n");
    }
    System.out.println(sb);
  }
}