[python] 백준 14501 - 퇴사

출처 : 백준, https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

 

풀이

 

if __name__ == '__main__':
  date = int(input())
  consult = [[0, 0]]

  for _ in range(date):
    consult.append(list(map(int, input().split())))
    
  matrix = [[0] * (date+1) for _ in range(date+1)]

  for j in range(1, date + 1):
    for i in range(1, date + 1):
      first = matrix[i][j-1]
      score = consult[j][1] if consult[j][0] + j -1 <= i else 0
      second = matrix[j-1][j-1] + score
      matrix[i][j] = max(first, second)

  print(matrix[date][date])

 

배낭 문제의 알고리즘에서 착안한 풀이. 2차원 DP를 이용해 1부터 올라가며 푼다.

시간 복잡도는 O(N^2)인데 끝나고 보니 DP를 이용한 O(N)인 풀이가 있더라.

해당 풀이는 하단에 적어놓았다.

 

---

 

시간 복잡도

 

O(N^2)

 

 

다른 사람의 풀이를 보면서 알게 된 점

 

DP를 이용한 O(N) 풀이

 

if __name__ == '__main__':
  n = int(input())
  T = []
  P = []
  pay = [0] * (n + 1)
  
  for i in range(n):
    tempT, tempP = map(int, input().split())
    T.append(tempT)
    P.append(tempP)

  for i in range(n-1, -1, -1):
    a = 0 if i+1 > n else pay[i+1]
    b = 0 if i+T[i] > n else pay[i+T[i]] + P[i]

    pay[i] = max(a, b)

  print(pay[0])

 

knapsack의 문제와 비슷하게 오늘 상담을 할지 말지에 따른 총 pay 값을 비교하며 푼다.

다른 점은 날짜를 거꾸로 내려오며 DP를 전개하는 풀이라는 점.

 

그래서 오늘 상담을 한다면, 상담을 하는데 T[i]만큼의 시간이 걸리므로,

오늘치 상담이 끝난 후인 i + T[i] 날짜까지 얻을 수 있는 총 페이와 오늘 치 페이 P[i]를 더한 값으로 설정하고

오늘 상담을 하지 않는다면, 다음날의 총 페이값을 가져와 오늘의 총 페이값으로 설정한다.

그리고 이 둘을 비교하여 더 큰 값을 오늘의 총 페이값으로 설정한다.

1일차까지 이를 반복한 후 1일차의 총 페이값을 출력하면 최대값이 나온다.

a, b를 구할 때 범위를 정확히 구하기 귀찮으면 그냥 try ~ except문을 사용해서 해도 되지 않을까 싶다.

 

결론적으로 점화식은

 

pay[i] = max(pay[i+1], pay[i+T[i]] + P[i]) 
#단, i+1 > n이라면 pay[i+1] = 0
#또, i+T[i] > n이라면 pay[i+T[i]] + P[i]가 아닌 0

 

DFS를 이용한 풀이

 

DFS는 트리 혹은 그래프 구조를 완전 탐색하는데 주로 쓰인다.

그러니까 DFS로 문제를 풀겠다는 말은 모든 경우의 수를 다 탐색해서 최대값을 찾아내겠다는 의미이다.

 

max_val = 0
stack = []

def DFS(start):
  global max_val
  
  if start >= n + 1:
    total = sum(stack)
    if total > max_val:
      max_val = total

    return
      
  for index in range(start, n+1):
    if index + T[index] <= n + 1:
      stack.append(P[index])
    
    DFS(index + T[index])

    if index + T[index] <= n + 1:
      stack.pop()

if __name__ == '__main__':
  n = int(input())
  T = [0]
  P = [0]
  
  for i in range(n):
    tempT, tempP = map(int, input().split())
    T.append(tempT)
    P.append(tempP)

  DFS(1)

  print(max_val)

 

시작 index부터 n까지 for문으로 stack에 넣고 빼면서  재귀호출한다.

이 때, stack에는 현재 시점에서 끝낼 수 있는 상담만 들어가야하므로

index + T[index] <= n + 1인 경우에만 stack에 추가하고 뺀다.

(7일 중에 index = 7, T[index] = 1인 경우도 추가되어야하므로 n + 1이다.)

 

만약 start가 n+1보다 크거나 같다면 stack에 있는 값을 sum하고 최대값과 비교 후 갱신한다.

이를 반복한다.

 

 

고찰

 

기존 DP는 오늘치 점수를 더해줄지 말지 여부가 과거나 현재에서 결정된다.

예를 들어 계단 오르기 문제에서 내가 밟고 있는 계단의 점수는 내가 계단을 밟은 순간(현재) 더해져야한다.

그러나 이 문제는 내가 보고 있는 날짜의 상담이 T일 뒤에 종료되므로 더해줄지 말지 여부가 미래에서 결정된다.

따라서 index를 거꾸로 오며 과거에서 결정되는 것처럼 형태를 바꿔주어 DP를 구성하면 쉽게 구성할 수 있다.