[BJ]14501 퇴사

BJ S3 14501 퇴사

 

 

문제링크

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

14501번: 퇴사

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=-4wjSUr1_K0 

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

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

/**
 * @author 은서파
 * @since 2021. 10. 19.
 * @see 
 * @performance 11680	96	
 * @category #
 * @memo
 */

public class BJ_S3_14501_퇴사{
	
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int N; //1 <=N <=15
	static int MAX;
	static int [][] data;
	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		data = new int [N+1][2];
		for(int n=1; n<=N; n++) {
			tokens = new StringTokenizer(input.readLine());
			data[n][0]=Integer.parseInt(tokens.nextToken());
			data[n][1]=Integer.parseInt(tokens.nextToken());
		}// 입력 완료!!
		
		powerSet(1, 0);
		System.out.println(MAX);
	}
	
	private static void powerSet(int today, int benefit) {
		// 우리가 찾는 최대값 - 결정 시점?
		MAX = Math.max(MAX, benefit);
		
		// 기저조건
		if(today==N+1) {
			return;
		}
		
		// 상담을 할때.. - 상담이 근무일 이내에 끝나야 상담 가능
		// 오늘이 7일이고 소요기간이 1일인 상담이 있다면?
		if(today + data[today][0]<=N+1) {
			powerSet(today + data[today][0], benefit + data[today][1]);
		}
		// 상담을 안할 때..
		powerSet(today+1, benefit);
	}
	
	// REMOVE_START
	private static String src = "7\n"
			+ "3 10\n"
			+ "5 20\n"
			+ "1 10\n"
			+ "1 20\n"
			+ "2 15\n"
			+ "4 40\n"
			+ "2 200";
	// REMOVE_END
	
}