[JAVA] 퇴사 - DFS

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

14501번: 퇴사

생각과정

- 날짜별 상담소요시간과 금액을 T, P 배열에 저장한다.

- 현재 날짜가 n이 될 때까지 재귀 함수를 호출한다.

- 재귀함수는 하루당 두 번 호출될 수 있는데, 각각 해당 날짜에 상담했을 경우와 하지 않았을 경우를 호출한다.

- 현재 날짜를 선택할 경우 상담소요시간이 퇴사 이전이어야 한다.

- 경우의 수를 구한 후 최댓값만 찾으면 되므로 DFS를 쓰면 간단히 풀 수 있는 문제다.

 

구현

import java.util.Scanner;

public class Main {
	public int maxP = 0;
	
	public void solution(int n, int[]T, int[]P, int day, int earnP) {
		if(day == n) {
			//종료
			maxP = Math.max(earnP, maxP);
			return;
		}
		
		//현재 날짜 선택
		if(n-day >= T[day]) {
			solution(n, T, P, day+T[day], earnP+P[day]);
		}
		
		//선택x
		solution(n, T, P, day+1, earnP);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int[]T = new int[n];
		int[]P = new int[n];
		for(int i=0;i<n;i++) {
			T[i] = s.nextInt();
			P[i] = s.nextInt();
		}
		
		Main b = new Main();
		b.solution(n, T, P, 0, 0);
		System.out.println(b.maxP);
	}

}

 

결과