πŸ“– [λ°±μ€€μ•Œκ³ λ¦¬μ¦˜ 풀이] Q.14501 퇴사 문제 풀이

πŸ“– 문제

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

μƒλ‹΄μ›μœΌλ‘œ μΌν•˜κ³  μžˆλŠ” λ°±μ€€μ΄λŠ” 퇴사λ₯Ό ν•˜λ €κ³  ν•œλ‹€.

μ˜€λŠ˜λΆ€ν„° N+1일째 λ˜λŠ” λ‚  퇴사λ₯Ό ν•˜κΈ° μœ„ν•΄μ„œ, 남은 N일 λ™μ•ˆ μ΅œλŒ€ν•œ λ§Žμ€ 상담을 ν•˜λ €κ³  ν•œλ‹€.

λ°±μ€€μ΄λŠ” λΉ„μ„œμ—κ²Œ μ΅œλŒ€ν•œ λ§Žμ€ 상담을 작으라고 뢀탁을 ν–ˆκ³ , λΉ„μ„œλŠ” ν•˜λ£¨μ— ν•˜λ‚˜μ”© μ„œλ‘œ λ‹€λ₯Έ μ‚¬λžŒμ˜ 상담을 μž‘μ•„λ†“μ•˜λ‹€.

상담을 적절히 ν–ˆμ„ λ•Œ, 백쀀이가 얻을 수 μžˆλŠ” μ΅œλŒ€ μˆ˜μ΅μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

πŸ” 접근법

Q.14501 퇴사 문제 ν’€μ΄μž…λ‹ˆλ‹€.

ν‡΄μ‚¬ν•˜κΈ° μ „κΉŒμ§€ μ΅œλŒ€ μˆ˜μ΅μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€.

상담 κ°€λŠ₯ν•œ λ‚ μ§œλ₯Ό μ „λΆ€ νƒμƒ‰ν•˜μ—¬

μ΅œλŒ€ μˆ˜μ΅μ„ ꡬ할 수 μžˆμŠ΅λ‹ˆλ‹€.

였늘 상담을 ν•˜κ±°λ‚˜ 내일 상담을 ν•˜λŠ” 경우λ₯Ό μž¬κ·€μ μœΌλ‘œ νƒμƒ‰ν•˜μ—¬

λͺ¨λ“  경우의 수λ₯Ό ꡬ해 λ³Ό 수 μžˆμŠ΅λ‹ˆλ‹€γ…£.

πŸ’» μ½”λ“œ


package problem.bfsdfs;

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

public class Main_14501 {

    static int N;
    static int t[];
    static int p[];
    static int max = -1;

    public static void main(String[] args) throws IOException {
        input();
        solve(1,0);
        System.out.println(max);
    }

    public static void solve(int index, int value) {
        if (index >= N+1) {
            max = Math.max(max,value);
            return;
        }
        if (index + t[index] <= N + 1) {
            solve(index + t[index], value + p[index]);
        }
        solve(index+1,value);
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        t = new int[N+1];
        p = new int[N+1];
        for(int i=1; i<=N; i++){
            String temp[] = br.readLine().split(" ");
            t[i] = Integer.parseInt(temp[0]);
            p[i] = Integer.parseInt(temp[1]);
        }
        br.close();
    }

}

Written on January 10, 2021