백준 14501 퇴사 (Python)

문제

출처: https://www.acmicpc.net/problem/14501

나의 접근법

상담 일정 전체를 탐색하는 반복문 안에 일정이 가능한지  확인하며 일정과 T를 확인하며 N+1이 넘어갈 때까지 while로 체크하며 해결하려고 했습니다.

하지만 이렇게 할 경우 예제1 은 1일 -> 4일 -> 5일은 찾지만 예제 4의 1일 -> 6일 -> 7일은 찾았지만 1일 -> 6일 -> 8일의 경우는 못 찾았습니다.

이 문제점을 찾았더니 DFS와 백트래킹이 생각나서 바로 구현 방식을 틀고 다음과 같이 작성하였습니다.

 

첫번째 코드

def dfs(startDate, period, pay):
    global ans # 상담하면 퇴사날이 넘어 가는 경우
    for i in range(startDate+period, N+1):
        T, P = arr[i]
        if not check(i, T):
            continue
        ans = max(ans, pay + P)
        dfs(i, T, pay+P)


def check(date, period):
    if date+period <= N+1:
        return True
    return False

N = int(input())
arr = [[]]
ans = 0
for i in range(1, N+1):
    arr.append(list(map(int, input().split())))

for i in range(1, N+1):
    T, P = arr[i]
    if check(i, T):
        dfs(i, T, P)

print(ans)

첫번째 코드는 인덱스 에러가 발생했습니다. 이유는 저는 i번째 일정에서 T 일 동안 상담을 해도 가능한지 check에 넣고 가능하다면 dfs를 넣는 방식으로 구현했습니다. 그리고 dfs 안의 for문은 다음 i+T 일 부터 반복을 시작했습니다. 하지만 이경우 arr[i]에서 범위를 벗어나서 먼저 check를 수행하지 않고 dfs에서 확인하는 것으로 바꿨습니다.

 

두번째 코드 (정답)

def dfs(startDate, period, pay):
    global ans
    if not check(startDate, period):
        return
    ans = max(ans, pay)
    for i in range(startDate+period, N+1):
        T, P = arr[i]
        dfs(i, T, pay+P)

def check(date, period):
    if date+period <= N+1:
        return True
    return False

N = int(input())
arr = [[]]
ans = 0
for i in range(1, N+1):
    arr.append(list(map(int, input().split())))

for i in range(1, N+1):
    T, P = arr[i]
    dfs(i, T, P)
print(ans)

후기

위 문제를 해결하고 다른 정답자들의 코드를 검색했더니 DP로 깔끔하고 간결하게 구현하는 방법을 배웠습니다. 저도 처음에 DP를 생각했다가 풀이가 바로 떠오르지 않아서 반복문을 통해서 해결했는데 DP 방법은 신기했습니다. 앞에서 부터 해결하는 것이 아니라 뒤에서 부터 큰 값을 가져오는 것이 핵심이었습니다.

	1일	2일	3일	4일	5일	6일	7일	8일
T	3	5	1	1	2	4	2
P	10	20	10	20	15	40	200
dp	45	45	45	35	15	0	0	0

이를 dp로 표현하면 다음과 같습니다.

 

N = int(input())
days = [0]
salary = [0]
dp = [0]
for i in range(N):
    T, P = map(int, input().split())
    days.append(T)
    salary.append(P)
    dp.append(P)
dp.append(0)

for i in range(N, 0, -1):
    if days[i]+i <= N+1: #6일에 2일 짜리 상담 있으면 6, 7로 가능해서 <=과 N+1로 함
        dp[i] = max(dp[i+1], dp[i]+dp[i+days[i]])
    else:
        dp[i] = dp[i+1]

print(dp[1])