[java]퇴사 - 백준14501

문제

• 퇴사(백준14501)

풀이

문제 해석을 하자면,

• 주어진 조건속에서 가장 많은 수익을 내게끔 상담일을 수행하여 최대 수익을 구하라
• 이때, 해당 날짜에 상담하는 일수 T도 함께 고려하여 예상하도록 노력하자

풀이

• 범위가 크지 않기 때문에 완전탐색 방식으로 전체를 dfs로 돌리면 되므로 간단하다.
• 단, idx>N+1 과 result = Math.max(result, val) 을 호출한 타이밍이 중요하다.

코드

public static int N;
public static long result;
public static Pair[] inArr=new Pair[20];
public static boolean[] visited=new boolean[20];

public static void dfs(long val, int idx) {
    //base condition
    if(idx>N+1) {
        return;
    }
    //recursion
    result = Math.max(result, val);
    for(int i=idx; i<=N; i++) {
        if(visited[i]) continue;
        visited[i]=true;
        Pair p = inArr[i];
        dfs(val+p.P, i+p.T);
        visited[i]=false;
    }
}

public static void main(String[] args) throws Exception {
    //init
    for(int i=0; i<20; i++) {
        inArr[i]=null;
        visited[i]=false;
    }
    result=0;
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    N = Integer.parseInt(br.readLine());
    for(int i=1; i<=N; i++) {
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        int T = Integer.parseInt(stk.nextToken()); // 시간
        int P = Integer.parseInt(stk.nextToken()); // 수익
        inArr[i] = new Pair(T, P);
    }
    //run
    for(int i=1; i<=N; i++) {
        if(visited[i]) continue;
        visited[i]=true;
        Pair p = inArr[i];
        dfs(p.P, i+p.T);
        visited[i]=false;
    }
    //output
    System.out.println(result);
}

static class Pair {
    int T; int P;
    public Pair (int T, int P) {
        this.T = T; this.P = P;
    }
}

느낀점

생략