외주 수익 최대화하기 (퇴사)

문제 출처 : 코드트리_외주 수익 최대화하기
티어 : 실버3
유형 : 백트래킹
출제 : 2017년 상반기 오전 2번
주의사항 : 없습니다.

---

골드가 두 문제 배치된 오후와 다르게 실버문제가 출제되었습니다. 이런걸 보면 운이 참 중요하기도 하다는 것을 느낍니다. 이번 문제도 푸는 방법이 크게 두 가지로 나뉘는데요, 하나는 백트래킹, 나머지 하나는 dp입니다. 후술하겠지만 최대 휴가일이 몇 천일, 몇 만일이 아니라 15일 뿐이므로(ㅠㅠ) 여기서는 백트래킹으로 풀이하겠습니다.

---

생각의 흐름

문제를 딱 보자마자, 각 날짜별로 최대화된 수익을 기록하는 dp문제구나, 라는 생각이 들었습니다. 하지만 휴가일의 최대가 15일인점으로 미루어보아 백트래킹으로 더 쉽게 구현할 수 있겠다고 생각하여 백트래킹을 이용하기로 했습니다. 각 날짜마다 할 수 있는 일을 했을 때와 하지 않았을 때를 구분하여 재귀를 돌리자고 마음먹고 문제를 풀었습니다.

 

스킬

스킬이라고 유난히 말씀드릴 만한 것은 없고, 재귀함수의 분기를 어떻게 나누었느냐에 대해 설명드리겠습니다. 알아두시면 다음 분기 별 백트래킹을 구현할 때 도움이 될 거에요. 먼저 휴가가 5일이라 가정했을 때 처음 dfs가 시작되는 상황을 봅시다.

해당 분기를 어떻게 나눌 수 있을까요? 우리는 첫번째 날에 주어진 일을 할 때와 하지 않을 때로 나누어서 다음 재귀로 돌입할 수 있을 겁니다. 1원의 수익을 주는 이틀짜리 일이므로 일을 했을 때는 2일과 1원을 인자로 가진 재귀로, 일을 하지 않았을 때는 1일과 0원을 인자로 가진 재귀로 돌입해주시면 되겠습니다.

 

dfs를 구현하였으니 다음은 1일 0원의 차례겠죠! 여기서도 마찬가지로 2일과 1원의 일이 배정되어있는데요, 이 일을 하지 않는다면 수익이 그대로인 채로 다음날(2일)에 도달하게 될 것이고, 일을 한다면 일이 끝난 3일째에 1원의 수익을 가진 채로 이동하게 되겠네요.

 

 

이런 식으로 dfs를 구현하겠습니다. 문제를 한번 풀어볼까요?

 

풀이

def getInput():
    # 입력받는 힘수
    global n, tasklist

    n = int(input())
    tasklist = [0]*n
    for i in range(n):
        tasklist[i] = list(map(int, input().split()))

def dfs(day, income):
    # 백트래킹 함수. 현재 날짜와 그 때의 수익
    global maxx

    if day>n:  # 일이 끝나는 날짜가 휴가기간 뒤라면
        return
    elif day==n:
        maxx = max(maxx, income)
        return
    

    # 각각 해당 일에 일을 시작안했을 때, 했을 때
    dfs(day+1, income)
    dfs(day+tasklist[day][0], income+tasklist[day][1])


# ===== 실제 실행하는 부분 =====
def main():
    global maxx

    getInput()
    maxx = -10
    dfs(0, 0)
    print(maxx)

main()