백준14501 퇴사

2021.06.12 퇴사

Solution

• DFS : 특정 일자에 상담이 가능한지 그 뒤(다음 깊이탐색)로 상담이 가능한지를 재귀적으로 깊이우선탐색합니다.

  재귀함수는 다음과 같이 구현할 수 있습니다.

  • 기저조건 : N+1일째 이상을 탐색할 경우 퇴사이므로 0을 리턴합니다.
  • 재귀함수 정의 : 특정 날짜를 입력받아 퇴사할때까지 상담으로 받을 수 있는 금액의 최댓값을 반환하는 함수
    • 해당 날짜의 고객을 상담할 수 있는지 확인합니다.
    • 상담할 수 있다면 금액을 초기값으로 설정하고, 다음 탐색할 노드들을 탐색하고 그 중 최댓값을 더해 반환합니다.

• DP : 특정 날짜에부터 퇴사일까지 받을 수 있는 최댓값을 메모이제이션합니다.

  재귀함수에서 DP에 기록이 되어있다면 반환하도록 하여, 중복된 탐색을 제거할 수 있습니다.

Source

1

# DP
# 2021.06.12

def DFS(table, memo, today, N):
    if today >= N:
        return 0

    if memo[today] >= 0:
        return memo[today]
    else:
        # can't work
        if today + table[today][0] > N:
            memo[today] = 0
        # can work
        else:
            ret = 0
            for i in range(today + table[today][0], N):
                ret = max(ret, DFS(table, memo, i, N))
            memo[today] = table[today][1] + ret
        return memo[today]

def getResult(table, memo, N):
    ret = 0
    for start in range(N):
        ret = max(ret, DFS(table, memo, start, N))
    return ret

N = int(input())
table = [tuple(map(int, input().split())) for _ in range(N)]
memo = [-1 for _ in range(N)]
# print(table)
print(getResult(table, memo, N))
# print(memo)

2

0일째 table을 1일, 0원으로 추가해서 재귀함수 하나로 결과 도출할 수 있도록 변경

# DP
# 2021.06.12

def DFS(table, memo, today, N):
    if today > N:
        return 0

    if memo[today] >= 0:
        return memo[today]
    else:
        # can work
        if today + table[today][0] - 1 <= N:
            ret = 0
            for i in range(today + table[today][0], N+1):
                ret = max(ret, DFS(table, memo, i, N))
            memo[today] = table[today][1] + ret
        # can't work
        else:
            memo[today] = 0

        return memo[today]

N = int(input())
table = []
table.append((1, 0))
memo = [-1] * (N+1)
for _ in range(N):
    table.append(tuple(map(int, input().split())))
# print(table)
print(DFS(table, memo, 0, N))