[백준 14501번] 퇴사 with Java

guswls·2024년 4월 26일

백준 백트래킹

알고리즘

목록 보기

8/39

문제

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

코드

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

class Main {
	static int N;
	static Work[] works;
	static int result = Integer.MIN_VALUE;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		works = new Work[N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			works[i] = new Work(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}

		backTracking(0, 0);

		System.out.println(result);
	}

	static void backTracking(int idx, int pay) {
		if (idx >= N) {
			result = Math.max(result, pay);
			return;
		}

		int updatedDate = works[idx].date + idx;
		if (updatedDate <= N) {
			backTracking(updatedDate, pay + works[idx].pay);
		} else {
			backTracking(updatedDate, pay);
		}

		backTracking(idx + 1, pay);
	}

	static class Work {
		int date;
		int pay;

		Work(int day, int money) {
			this.date = day;
			this.pay = money;
		}
	}
}

문제 이해

문제에 나온 표를 보면 문제를 쉽게 이해할 수 있다.
상담에 걸리는 기간의 합이 N보다 작으면서 각 상담의 비용의 합이 최대인 경우를 구하면 된다.

풀이 방법

백트래킹으로 문제를 해결하였다.
기본적으로 idx를 1씩 증가시키며 백트래킹을 진행한다.
works[idx].date + idx는 그 일을 수행한 후의 Date가 된다. 예를 들어 works[0]의 date가 3이라면, 그 일을 끝낸 후에는 3일째가 되는 것이다.
위에서 구한 날짜가 N보다 작다면 day와 pay를 갱신한 후 dfs를 호출, 만약 크다면 더이상 pay를 갱신하지 말고 day만 갱신한다.
만약 idx가 N보다 크거나 같다면, result와 pay중 더 큰 값을 비교하고 종료한다.