알고리즘/BOJ

[BJ]14501 퇴사

  • -

BJ S3 14501 퇴사

 

 

문제링크

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

 

14501번: 퇴사

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

www.acmicpc.net

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

 

동영상 설명

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

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 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
	
}

 

'알고리즘 > BOJ' 카테고리의 다른 글

[BJ]G5 14503 로봇청소기  (0) 2021.10.28
[BJ]백준 15486. 퇴사2  (0) 2021.10.20
[BJ]백준 14499 주사위굴리기  (0) 2021.10.15
[BJ]BJ G5 3190 뱀  (0) 2021.10.12
[BJ]BJ G2 12100 2048(Easy)  (0) 2021.10.04
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.