문제
문제는 꽤나 간단하다.
그냥 퇴사하기 전에 최대의 수익, (P)를 더해서 가질 수 있는 최댓값을 구하면 된다.
여기서 고려해야 할 것은 T에 있는 기간을 고려해야 한다는 것
1. 총 3일이 걸리는 일이 있다면 1일에 시작했을 때 4일까지 다른 일을 하지 못 함
2. 퇴사 전날에 2일 이상 걸리는 일을 맡을 수 없음
이정도만 알면 문제는 다 이해한 것이다.
알고리즘
(백준에 나와있는 예시를 생각했을 때)
처음에 알고리즘을 짤 때 단순히 1일에 시작하고 4일에 다른 일 시작하고 5일에 시작 이런식으로 짰었다. 이를 2일, 3일도 계속해서 반복했다.
여기서 우리가 알아야 할 것은 1일에 시작해서 4일, 5일에 일을 끝내더라도 6일에 있는 일이 수익(P)가 더 크다면 하루는 쉬고 6일째에 있는 일을 하는 것이 훨씬 효율적이라는 것이다.
즉, 바로 시작이 아니라 다음 배열에 있는 값을 더해가면서 하나씩 비교를 해야한다는 것이다.
그래서 내가 활용한 것은 백트래킹이다.
먼저 일을 시작하는 날은 1, 2일 이런식으로 하루씩 늘려간다.
첫번째 일이 끝나고 바로 현재 있는 일을 선택할 수 있다 -> 이 경우에는 재귀함수를 이용하여 일이 끝날 새로운 날짜, 그때의 수익을 갱신하여 넘겨준다.
현재 일을 하지 않는다. -> 재귀함수를 이용하여 날짜만 하루 증가하여 넘겨준다.
이 모든 값들을 전부 비교하여 profit에 저장하면서 현재의 최댓값, maxProfit과 비교한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[][] tp;
public static int maxProfit = 0; // 최대 수익
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
tp = new int[N][2];
for (int i=0 ; i<N ; i++) {
st = new StringTokenizer(br.readLine());
tp[i][0] = Integer.parseInt(st.nextToken());
tp[i][1] = Integer.parseInt(st.nextToken());
}
find(0, 0); // 백트래킹 implement
System.out.println(maxProfit);
}
public static void find(int day, int profit) {
if (day >= N) { // 현재 날짜가 퇴사일을 넘어가면 현재 가지는 profit을 저장하고 종료
maxProfit = Math.max(maxProfit, profit);
return;
}
// 일이 끝나고 바로 당장 일을 시작한다면
if (day + tp[day][0] <= N) {
// 새로운 일이 끝날 날짜와 그때 얻을 수익을 더해서 재귀함수로 다시 던져준다
find(day + tp[day][0], profit + tp[day][1]);
}
// 일이 끝나고 당장 일을 시작하지 않는다면 내일로 날짜를 변경하여 재귀함수로 던져준다
find (day+1, profit);
}
}결과적으로 나는 이런 코드를 작성했다.
마무리
재귀함수는 트래킹을 머릿속으로 하는 게 참 어렵다...
그래도 하나씩 생각하면서 정리하다보면 이해가 잘 되는 것 같다.
하나씩 차근차근 해나가야지
