[백준] 14501 퇴사 - Brute Force / Java

• 문제 링크

14501번: 퇴사

 

• 풀이 과정

해당 문제는 재귀를 활용하여 완전 탐색(Brute Force) 으로 해결하거나 동적 계획법(DP) 으로도 해결 가능하다.

아래 링크에서 내용은 같지만 N의 범위가 넓은 "퇴사 2" 는 DP로 해결했고 이 문제는 완전 탐색으로 풀이했다.

[백준] 15486 퇴사 2 - DP /Java

 

우선 총 상담일의 수 n과 각각의 지정된 상담 소요일과 수익을 t배열, p배열 전역변수에 저장해

실제 비교를 진행할 comp 함수에서도 사용 가능하게 설정해둔다.

또한 시작일이 1일이 아닐 수도 있기에 모든 경우의 최대 수익을 cnt 변수에 저장해 비교한다.

 

우선 현재 날짜 + 상담 소요일, 즉 i + t[i] 를 comp 함수의 첫번째 매개변수로 입력받는다.

그 값이 n + 1 이하로 주어진 총 상담일을 초과하지 않을 시 함수가 진행된다.

두번째 매개변수로 입력받은 값은 현재까지 총 수익이며 이를 temp 변수에 저장하고

반복문은 i + t[i]부터 시작, 이는 각각의 상담 소요일이 경과되었음을 의미한다.

 

그리고 현재 수익과 다음 수익을 Math.max 함수로 비교하는데,

다음 수익은 comp 함수가 재귀적으로 실행되어 구해진다.

이 역시 현재까지 날짜에 이번 상담 소요일이 더해진 i + t[i] 가 첫번째 매개변수로 전달되며,

현재까지 수익과 이번 상담일에 벌어들일 수익을 더한 값,

즉 pay + p[i]가 두번째 매개변수로 반복문의 comp 함수에 전달된다. 

 

이런 식으로 최대 수익이 재귀적으로 temp 변수에 저장되고 i + t[i] > n + 1 까지 진행되면

최종적으로 Math.max 로 비교하여 갱신된 temp 값이 정답으로써 반환된다. 

 

• 풀이 코드

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

public class Main {

	static int n;
	static int[] t;
	static int[] p;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		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());
		}

		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			cnt = Math.max(cnt, comp(i + t[i], p[i]));
		}

		bw.write(cnt + "\n");
		bw.flush();
	}

	private static int comp(int day, int pay) {
		if (day > n + 1)
			return 0;

		int temp = pay;
		for (int i = day; i <= n; i++) {
			temp = Math.max(temp, comp(i + t[i], pay + p[i]));
		}

		return temp;
	}
	
}