Chap 16. DP - Q33. 퇴사

  • 0
  • 0
0
0

1. 퇴사

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))

a. 🙄 회고

내 풀이

  • 상담료가 최대가 되는 경우를 찾아야 한다.
  • 1일 -> 7일 순서로 푸는 방법밖에 없다고 생각했다.
    • 7일 -> 1일 순서는 전날 상담을 며칠동안 할건지 알 수 없기 때문에 불가능하다고 생각했다.

반성

  • DP문제는 문제의 조건을 잘 생각해서 어떻게하면 잘 역을 수 있을지를 생각해야한다.

결론

  • DP는 어렵다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

a. 책 답안

python-for-coding-test/3.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

14501번: 퇴사 (acmicpc.net). Baekjoon. (accessed Oct 27, 2021)

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.