[BOJ-14501] 퇴사 -Java

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

14501번: 퇴사

package 시뮬레이션_review;

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

public class 퇴사 {
	static int N,t[],p[],result;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N=Integer.parseInt(br.readLine());
		t=new int[N+1];
		p=new int[N+1];
		
		for(int i=1; i<=N; i++) {
			st=new StringTokenizer(br.readLine());
			t[i]=Integer.parseInt(st.nextToken());
			p[i]=Integer.parseInt(st.nextToken());
		}
		dfs(1,0);
		System.out.println(result);
	}
	private static void dfs(int day, int money) {
		if(day>=N+1) {
			result=Math.max(result, money);
			return;
		}
		
		for(int i=day; i<=N; i++) {
			if(day+t[i]<=N+1) dfs(day+t[i], money+p[i]);
			else dfs(day+t[i], money);
			day++;
		}
		
	}
	

}

소요시간 : 25분

 

시험감독과 마찬가지로 이런문제가 코테에 나온다면 너무 행복할듯...

 

그냥 DFS돌리면 바로 답이 나옵니다

 

DFS돌릴 때 좀 중요한게 만약 선택하지 않았따면 DAY를 1일 늘려줘야 합니다.

 

현재 DAY가 4인데 DAY4를 선택하지 않았다면 DAY를 1 늘려줘야 하기때문에 

 

DFS안의 포문의 가장 밑에 DAY++을 해줬습니다~