[백준 14501]. 퇴사 (Java) - 완전탐색

문제

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

알고리즘

완전탐색

 

 

풀이

완전탐색을 통해 상담할 수 있는 모든 경우의 수를 구한다음 최대 값을 구해주어 풀었다.

1개 의 상담에 대해 선택 O/X하는 2가지의 경우가 존재하므로 전체 N개 상담에 대한 최대 경우의 수 = 2^n => 32,768이다.

조건 값이 적어서 그렇지 많게 되면 dp로 풀어야한다.

 

 

코드

package com.company;

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

public class Test_BruteForce2 {
    static int N;
    static ConsultingInfo[] arr;
    static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        arr = new ConsultingInfo[N];

        for (int i = 0; i < N; i++) {
            int T, P;
            StringTokenizer st = new StringTokenizer(bf.readLine());
            T = Integer.parseInt(st.nextToken());
            P = Integer.parseInt(st.nextToken());

            arr[i] = new ConsultingInfo(T, P);
        }

        consulting(0, 0);
        System.out.println(ans);

    }

    static public void consulting(int idx, int totalPrice) {
        if (idx >= N) {
            ans = Math.max(ans, totalPrice);
            return;
        }

        for (int i = idx; i < N; i++) {
            int nextIdx = i + arr[i].t;
            if(nextIdx>N){ //마지막 날짜가 N+1일 경우는 price를 더 하지 않는다.
                consulting(nextIdx, totalPrice);
            }else {
                consulting(nextIdx, totalPrice + arr[i].p);
            }
        }
    }

    static public class ConsultingInfo {
        int t;
        int p;

        public ConsultingInfo(int t, int p) {
            this.t = t;
            this.p = p;
        }
    }
}

 

dp풀이는 아래 블로그를 참조하자.

https://mingmeng030.tistory.com/166