Chap 16. DP - Q33. 퇴사

@mildsalmon·2021-10-27 11:25

1. 퇴사

난이도
- 중
풀이 시간
- 30분
시간 제한
- 2초
메모리 제한
- 512 MB
출처
- 14501번: 퇴사 (acmicpc.net)

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 1차 시도 (실패)


n = int(input())
array = []

for i in range(n):
    temp = list(map(int, input().split()))

    array.append(temp)

# array.append([0, 0])

dp = [0] * (n+1)

for i in range(n):
    t, p = array[i]
    # temp = array[t+i][0]
    # j = [i]
    save_day = []
    if i + t <= n:
        temp = i

        while temp + array[temp][0] < n:
            save_day.append(temp)
            temp += array[temp][0]

    # print(j)
    for a in save_day:
        dp[i] += array[a][1]

print(max(dp))

b. 😊 2차 시도 (성공, 책 답안 코드 보고 참고해서 품)


n = int(input())
array = []

for i in range(n):
    temp = list(map(int, input().split()))

    array.append(temp)

# array.append([0, 0])

dp = [0] * (n+1)

for i in range(n-1, -1, -1):
    next_day = array[i][0] + i
    answer = max(dp)

    if next_day <= n:
        dp[i] = max(dp[next_day] + array[i][1], answer)
    else:
        dp[i] = answer

answer = max(dp)

print(answer)

c. 😊 3차 시도 (2차 시도 코드랑 동일한데, 메모리를 덜 사용하는 방법)


n = int(input())
array = []

for i in range(n):
    temp = list(map(int, input().split()))

    array.append(temp)

# array.append([0, 0])

dp = [0] * (n + 1)

for i in range(n - 1, -1, -1):
    next_day = array[i][0] + i

    if next_day <= n:
        dp[i] = max(dp[next_day] + array[i][1], max(dp))
    else:
        dp[i] = max(dp)

print(max(dp))

d. 😊 4차 시도 (문제 해설하다가 코드가 이상해서 다시 품)


n = int(input())
array = []

for i in range(n):
    temp = list(map(int, input().split()))

    array.append(temp)

# array.append([0, 0])

dp = [0] * (n + 1)

for i in range(n - 1, -1, -1):
    next_day = array[i][0] + i

    if next_day <= n:
        dp[i] = max(dp[next_day:]) + array[i][1]

print(max(dp))