[백준] 14501번 / Java / 퇴사 - 재귀풀이

문제 - (https://www.acmicpc.net/problem/14501)

ssafy 준비하려고 CT공부할때 풀어봤던 문제랑 유사한 알고리즘이다.

나는 완전탐색으로 풀었다

 

 

 

 

 

📌주의할 점

예제를 중심으로 설명하자면, 1일에 상담하기로 했다면 3일 뒤까지는 상담을 진행할 수 없다. 하지만 1일에 상담하기로 하지 않고 그냥 2일로 넘어갈 수도 있다! 이 경우를 고려해야 한다.

 

 

 

😅실수

• 재귀내를 반드시 for문으로 구성할 필요가 없는데 계속 for문을 고집해서 시간을 잡아먹었다
• 재귀에 진입시에 세가지 조건을 생각해야 한다
  1) 일을 할 수 있나? = k가 n보다 작다
  2) 일을 할 수 없나? = k가 n보다 크다
  3) n일이 되었나?  = k가 n과 같다

 

 

코드를 보려면 '더보기' 클릭

package boj.samsungSWtest;

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

/**
 * 그냥 엄청 오래품.. 한 3시간 붙잡은듯..... 풀이를 봤다
 */
public class Resignation {
    static int n;
    static int[] t;
    static int[] p;
    static int max_money = Integer.MIN_VALUE;

    static void answer(int k, int money) {
        // 기저
        if (k > n) return;
        if (k == n) {
            max_money = Math.max(max_money, money);
            return;
        }

        answer(k + t[k], money + p[k]);
        answer(k + 1, money); /* 이게 포인트!! */
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        t = new int[n];
        p = new int[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }

        answer(0, 0);

        System.out.println(max_money);
    }
}