BOJ 14501. 퇴사 / BOJ 15486. 퇴사 2

14501번: 퇴사 (acmicpc.net)

14501번: 퇴사

처음 봤을 때는 상당히 난해했었고, 예전에 정렬로 풀었던 문제인 BOJ. 1931 회의실 배정이 떠올라서 헷갈렸었다.

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

 

그런데 회의실 배정같은 경우, 무조건 일정한 기간 안에 최대한의 회의 개수를 넣어야 하는 것이 목적이었다면,

이것은 각 작업마다 가중치가 정해져있어서 그리디 알고리즘으로는 풀 수 없다는 결론이 났다.

 

그리디 알고리즘 접근

가정) 기간이 가장 짧게 걸리는 상담들을 배치하면 상담을 하는 횟수가 많아지게 되고 가장 많은 이득을 얻을 것이다.

반례) 기간이 가장 길더라도 압도적인 금액을 받게 된다면 가장 긴 기간의 상담을 하는 것이 더 많은 이득을 얻을 수 있다.

따라서 그리디 알고리즘은 적절하지 못한 접근 방법이다.

 

풀이

DP를 이용해 풀 수 있는데, 점화식을 다음처럼 세워보았다.

1) i 날의 작업은 Ti 날이 지나야 완료됨.

2) DP[i]는 그 이전까지의 최대 이익 + 그 날에 마무리되는 작업 중 최대치 이다.

3) 따라서 i날의 작업은 DP[i-1]에 Pi를 더한 값으로 i+Ti 날에 완료된다.

4) DP[k]는 k날에 벌어들일 수 있는 이익 중 가장 큰 값이다.

 

1-based index 이므로 마지막에 dp[n] 이어야하는데 dp[n-1]로 잘못 적어서 한번 틀렸다.

주의하자.

 

 

15486번: 퇴사 2 (acmicpc.net)

15486번: 퇴사 2

퇴사 2는 퇴사 1과 완전히 똑같은 구조의 문제지만 테스트 케이스가 훨씬 많아졌다.

즉 시간안에 통과하는지를 봐야 한다.

 

기존의 알고리즘을 그대로 대입해보자.

pypy3으로 돌려야 간신히 1.7초 안에 통과하는 모습이다.

이정도만 해도 아주 훌륭한 알고리즘이고, 그냥 넘어가도 괜찮겠지만 한가지 의문이 생겼다.

시간을 더 줄일 순 없을까?

 

정답은 있었다.

지금 나는 candidate 배열을 이용해 각 날에서 가장 큰 값을 찾아 대입하고 있는데

이럴 필요 없이 바로 큰값들을 넣어주면 되는 것이었다.

 

풀이

1. i 번째 날에서 우리는 해당 날의 작업을 할지/ 안할지 결정할 수 있다.

2. 만약 하게 된다면 i+t-1 번째 날에 해당 작업이 완료될 것이다.

3. 그런데 이미 i+t-1 번째 날에 완료되는 작업들 중에 보수가 가장 큰 날이 있을 수 있다.

4. 그러므로 dp[i+t-1] 보다 dp[i-1] + p 가 더 클 경우에만 새로고침을 해준다.

5. i번째 날에 아무것도 안할 경우가 있으므로 dp[i]와 dp[i-1] 중 큰 값을 업데이트 해준다.

 

 

약 0.4초 정도 줄어들었다.