[JAVA] 백준 14501번

www.acmicpc.net/problem/14501

14501번: 퇴사

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, max=0;
    static boolean[] sch, select;
    static ArrayList<counsel> arr = new ArrayList<>();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        sch = new boolean[N + 1];     // 스케줄 잡혀있는 날인지? 0 dummy
        select = new boolean[N+1];    // 잡힌 상담인지? (pay계산 위함) 0 dummy
        arr.add(new counsel(0, 0)); // dummy
 
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr.add(new counsel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        
        // 가능한 경우 탐색
        search(1);
        
        System.out.println(max);
 
    }
 
    // 가능한 경우의 수
    static void search(int srcIdx) {
 
        if (srcIdx > N) {
            // 소득 max 비교
            max = Math.max(max, cal());
            return;
        }
 
        // 상담 끝나는 날
        int end = srcIdx+arr.get(srcIdx).day-1;
        
        // 스케줄이 잡혀있지 않은 날이면서 상담이 끝나는 날이 퇴사 전날이면 상담 가능
        if(!sch[srcIdx] && end <= N) {
            select[srcIdx] = true;
            for(int i=srcIdx; i<=end; i++) {
                sch[i] = true;
            }
            search(srcIdx + 1);
            
            select[srcIdx] = false;
            for(int i=srcIdx; i<=end; i++) {
                sch[i] = false;
            }
            search(srcIdx + 1);
        } else {
            search(srcIdx + 1);
        }
    }
    
    // 소득 계산
    static int cal() {
        int sum = 0;
        for(int i=1; i<=N; i++) {
            if(select[i]) {
                sum += arr.get(i).pay;
            }
        }
        return sum;
    }
 
}
 
class counsel {
    int day;
    int pay;
 
    counsel(int day, int pay) {
        this.day = day;
        this.pay = pay;
    }
 
}