백준] 14501 퇴사 (완전탐색으로 풀기 / Java)

백준] 14501 퇴사 (완전탐색으로 풀기 / Java)

---

언어 : Java

풀이 방법 : 완전탐색(Brute Force)로 풀기

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

14501번: 퇴사

혹시! 15486 퇴사2 풀이가 궁금하다면? 아래 링크로!

2020/02/27 - [개발/알고리즘 풀이] - 백준] 15486 퇴사2 ( DP/ Java )

백준] 15486 퇴사2 ( DP/ Java )

간단한 문제 설명

백준이가 상담을 하면서 얻을 수 있는 최대 수익을 출력하는 문제이다.

 

풀이 과정

완전 탐색, 모든 경우의 수를 다 해보는 방법을 선택했다.

1. 먼저 해당 날짜(index)에 상담을 할 수 있는지 없는지 판단하고

2. 상담을 할 수 있으면 상담일과 상담 수익을 더해서 재귀돌린다.

3. 혹시 오늘 상담을 안할 경우 얻는 수익이 더 클 경우를 위해서 오늘 상담을 할 수 있든지 없든지 상관없이 상담을 안해보는 경우를 추가한다.

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
 
/*
 * 퇴사
 * 완전탐색(Brute Force)으로 풀기
 */
public class Main_14501_퇴사 {
 
    private static int[][] arr;
    private static int N;
    private static int max;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(in.readLine());
        arr = new int[N+1][2];
        
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        //-------------입력부
        
        go(1, 0);            
        
        System.out.println(max);
 
    } // end main
 
    private static void go(int index, int sum) {
        
        if(max < sum)
            max = sum;
        
        if(index > N)
            return;
        
        // 내가 오늘(index) 상담을 할 수 있는지 검사
        int tmp = index + arr[index][0];
        if(tmp <= N + 1) {
            go(tmp, sum + arr[index][1]); // 오늘(index) 상담 해보기
        }
        go(index + 1, sum); // 오늘(index) 상담 안해보기
        
    } // end go
 
} // end class