SWEA 1952. [모의 SW 역량테스트] 수영장 :: 돼지개발자

출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq

"완전 탐색, 매달 이용하냐 안하냐"

문제를 풀면서 완전 탐색을 생각했다. 뭔가 이런 비슷한 문제를 예전에 점화식으로 풀었던 문제가 기억났는데, 사실 이해를 못함. 문제는 단순히 이용 계획이 0 일 이상인 월에 대해서 3가지 이용권으로 모두 탐색을 했다. (1년 이용권의 경우 한번만 체크) 어렵지 않았던 문제였다.

단, 이용 계획이 0인 달에는 재귀호출할 때 금액을 올리지 않는다. 이 부분만 고려하면 쉽게 풀렸다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int T;
    static int[] money = new int[4];
    static int[] plan = new int[12];
    static int min;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        
        int t = 1;
        while(T-- >0) {
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for (int i = 0; i < 4; i++) {
                money[i] = Integer.parseInt(st.nextToken());
            }
            
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 12; i++) {
                plan[i] = Integer.parseInt(st.nextToken());
            }
            
            min = money[3];
            solve(0,0);
            System.out.printf("#%d %d%n",t++,min);
        }
    }
    
    static void solve(int cur, int sum) {
        
        if(cur >= 12) {
            min = Math.min(min, sum);
            return;
        }
        
        if(plan[cur] == 0) {
            solve(cur+1,sum);
        }
        else {
            solve(cur+1,sum+(plan[cur]*money[0]));
            solve(cur+1,sum+money[1]);
            solve(cur+3,sum+money[2]);
        }
    }
}