[백준 14501] - 퇴사(JAVA)

[문제]

출처 - https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

---

[문제 풀이]

• DP를 사용해서 풀 수 있지만 N 조건이 15 이하라 사용하여 해결할 수 있다.
  
  • 해당 날에 일을 할 수 있다/없다 라는 조건으로 계산한다. 최대 2^15 = 32768 이기 때문에 가능하다.
• 1. 정답을 찾은 경우 // 2. 불가능한 경우 // 3. 다음 경우 세 가지를 구현하여 문제를 풀 것이다.

 

아래 소스 코드와 주석을 참고하면 된다.

---

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int t[];
	static int p[];
	static int n;
	static int ans = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		t = new int[n];
		p = new int[n];
		
		for(int i=0; i<n; i++) {
			StringTokenizer st  = new StringTokenizer(br.readLine());
			
			t[i] = Integer.parseInt(st.nextToken());
			p[i] = Integer.parseInt(st.nextToken());
		}
		go(0,0);
		
		System.out.println(ans);
		
	}

	public static void go(int index, int sum) {
		//1. 정답을 찾은 경우
		//해당 날이 퇴사하는 날 일때 최대 수익을 계산한다.
		if(index == n) {
			if(ans < sum) ans = sum;
			return;
		}
		
		//2. 불가능한 경우
		//퇴사하는 날을 넘었을 경우.
		if(index > n) return;
		
		//3. 다음 경우 
		// 일을 하게 되면 현재 일수에 걸리는 기간과 비용을 추가해 준다.
		go(index + t[index], sum+p[index]);
		
		//일을 하지 않게 되면 하루가 지나가고 비용은 그대로 이다.
		go(index+1, sum);
			
	}
}