채우다

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

• 풀이방법[알고리즘]

백준이가 퇴사하기 전까지 가장 많은 돈을 벌 수 있는 경우를 계산해야 하는 문제. 백트래킹 완전 탐색으로 풀 수 있는 문제이다. 상담을 받으면 해당 상담이 걸리는 날과 벌 수 있는 돈을 더해서 다음 상담 가능한 날로 점프하고, 받지 않으면 그대로 날짜만 +1해준다. 처음엔 생각없이 0번째 날을 무조건 넣어서 4번 예제에서 틀렸다. 0번째 날을 포함하지 않는 경우의 수도 계산해야 하기 때문에 date+1의 값을 넣어서 dfs를 구해주면 최대 벌이를 구할 수 있는 식이 나온다.

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

public class 퇴사 {
	static int N,answer;
	static ArrayList<Left> arr;
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new ArrayList();
		answer = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr.add(new Left(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
		}		
		dfs(0,0);
		System.out.println(answer);
	}
	
	static void dfs(int date,int sum) {
		if(date>=N) {
			answer = Math.max(answer, sum);
			return;
		}
		Left tmp=arr.get(date);
		if(date+tmp.T>N) {
			dfs(date+1,sum);
		}else {
			dfs(date+tmp.T,sum+tmp.P);
		}
		
		//첫번째 값을 넣는다고 무조건 되는게 아니니까 그 다음값부터 넣는것도 해봐야함!!!
		dfs(date+1,sum);

	}
	
	
	static class Left{
		int T,P;
		public Left(int T, int P) {
			this.T = T;
			this.P =P;
		}
		public String toString() {
			return T+"&"+P;
		}
	}
}