백준 14501번: 퇴사 (JAVA) <백트래킹 알고리즘 응용>

 

문제 해석

 

백준이는 N일까지만 상담일을 할 수 있다. 상담일은 최소 하루가 소요되고 당일을 포함한다. 

N과 각 날마다의 상담 소요시간, 페이가 입력으로 주어질 때 최대 수익을 얻을 수 있는 스케줄을 짜 최대 수익을 출력한다. 

 

알고리즘

 

상담일을 하는 것을 함수로 뒀을 때 퇴사 전까지 계속해서 일을 해야하므로 재귀적으로 상담일 함수를 호출한다.

위의 예시에서 1일에 일을 한다면 2일, 3일은 일을 못하므로 그때의 데이터는 사용할 필요가 없다. 

상담 소요시간 T를 이용하여 일하지 못하게 되는 날은 건너 뛰어서 상담일 함수를 재호출하고 퇴사날을 넘어가는 것에 대해서만 조건을 달아주면 된다. 

1일에 첫 근무를 시작하는 것부터 하여 2일에 첫 근무, 3일에 첫 근무 ... N일에 첫 근무할 때의 경우들을 모두 조사하여 최댓값만 남도록 한다.

 

코드

 

idx는 시작 날짜, pay는 현재 얻을 수 있는 돈이다.

날짜는 1일부터 시작하지만 인덱스가 0부터 시작하는 것을 염두한다.

resolve 함수 부분을 보면

idx가 n보다 크거나 같으면 pay와 maxPay를 비교하여 큰 값을 maxPay에 저장한다.

idx날에 일을 했을 때 소요시간을 더해 N보다 작거나 같다면 일을 할 수 있으므로 가능한 경우이고

다음 일을 위해 idx와 pay를 증가시킨 후 resolve를 재귀 호출한다.

idx날에 일을 할 수 없는 경우 이전까지의 pay가 최대이므로 pay는 그대로 두고 idx만 증가시켜 탈출할 수 있도록 해준다.

resolve(idx+1, pay)로 인해 일을 안하고 날을 넘겨 다른 날에 일하는 루트도 모두 조사할 수 있다.

ex) 1일에 일하고 다음 일할 수 있는 날인 3일에 일을 하지 않고 4일에 일을 재개하는 경우

 

문제에서 예시를 활용한 함수 진행 순서도

 

1차 호출: idx=0 / pay=0 / resolve(3, 10)

2차 호출: idx=3 / pay=10 / resolve(4, 30)

3차 호출: idx=4 / pay=30 / resolve(6, 45)

4차 호출: resolve(8, 45)

5차 호출: maxPay=45 / resolve(8, 45) 종료

3차 호출: idx=4 / pay=30 / resolve(5, 30)

6차 호출: resolve(9, 30)

7차 호출: maxPay=45 / resolve(9, 30) 종료

6차 호출: idx=5 / pay=30 / resolve(6, 30)

 

이런 식으로 가능한 모든 스케줄을 조사하고 최댓값만 남도록 할 수 있다.