퇴사

In [1]:

import sys, random
sys.setrecursionlimit(10000)
sys.path.append("/home/swyoo/algorithm/")
from sys import stdin
from utils.verbose import logging_time
from collections import defaultdict
# from utils.generator import random2D

14501. 퇴사

Parse Data

In [2]:

stdin = open('data/retire.txt')
input = stdin.readline
n = int(input())
consults = [tuple(map(int, input().split())) for _ in range(n)]
print(n, consults)

10 [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10)]

Naive DFS

Time complexity: $O(2^n)$

In [3]:

@logging_time
def solution1(consults):
    ans = 0
    def dfs(i, les):
        nonlocal ans
        if i >= len(consults):
            ans = max(ans, les)
            return
        Ti, Pi = consults[i]
        if i + Ti <= len(consults):
            dfs(i + Ti, les + Pi)
        dfs(i + 1, les)
    dfs(i=0, les=0)
    return ans
print("ans:", solution1(consults, verbose=True))

WorkingTime[solution1]: 0.54526 ms
ans: 55

Generate Data and Test

In [4]:

n = 40
consults = [(random.randint(1, 5), random.randint(1, 1000)) for _ in range(n)]
consults[:5] 

[(5, 31), (5, 746), (3, 715), (2, 296), (5, 25)]

In [5]:

solution1(consults, verbose=True)

WorkingTime[solution1]: 4345.19005 ms

8065

DFS + memoization

Both optimal substructure, overlapping subplems are satisfied.
Therefore, dynamic programming can be possible.
Recursion is as follows.

\[\begin{align} O_{i}^* &= \begin{cases} max(O_{i + 1}^*, O_{i + Ti}^*), & \text{o.w }\\ 0, & \text{if } i \ge n \\ \end{cases} \end{align} ,\text{where } 0 \le i < n\]

Time complexity: $O(n)$

In [6]:

@logging_time
def solution2(consults):
    ans, memo = 0, {}
    def dfs(i):
        if i in memo: return memo[i]
        if i >= len(consults): return 0
        Ti, Pi = consults[i]
        case1 = dfs(i + Ti) + Pi if i + Ti <= len(consults) else 0
        case2 = dfs(i + 1)
        memo[i] = max(case1, case2)
        return memo[i]
    ans = dfs(i=0)
    return ans
solution2(consults, verbose=True)

WorkingTime[solution2]: 0.02837 ms

8065

In [7]:

n = 40
consults = [(random.randint(1, 5), random.randint(1, 1000)) for _ in range(n)]
consults[:5] 
print(solution1(consults, verbose=True))
print(solution2(consults, verbose=True))

WorkingTime[solution1]: 2602.70357 ms
9707
WorkingTime[solution2]: 0.02837 ms
9707

Discuss

This is bottom up approach.

In [8]:

@logging_time
def dynamic(consults):
    dp, n = defaultdict(int), len(consults)
    for i in range(n - 1, -1, -1):
        Ti, Pi = consults[i]
        if Ti + i > n:
            dp[i] = dp[i + 1]
        else:
            dp[i] = max(dp[i + 1], Pi + dp[i + Ti])
    return dp[0]
dynamic(consults, verbose=True)

WorkingTime[dynamic]: 0.01812 ms

9707

In [9]:

n = 10000
consults = [(random.randint(1, 5), random.randint(1, 1000)) for _ in range(n)]
consults[:5] 
# print(solution1(consults, verbose=True))
print(solution2(consults, verbose=True))
print(dynamic(consults, verbose=True))

WorkingTime[solution2]: 8.02875 ms
2354484
WorkingTime[dynamic]: 3.90100 ms
2354484

Summited Code

No memoization

In [10]:

from sys import stdin
input = stdin.readline
stdin = open('data/retire.txt')
input = stdin.readline
n = int(input())
consults = [tuple(map(int, input().split())) for _ in range(n)]

def solution(consults):
    ans = 0
    def dfs(i, les):
        nonlocal ans
        if i >= len(consults):
            ans = max(ans, les)
            return
        Ti, Pi = consults[i]
        if i + Ti <= len(consults):
            dfs(i + Ti, les + Pi)
        dfs(i + 1, les)
    dfs(i=0, les=0)
    return ans
print(solution(consults))

55

Memoizaion

In [11]:

from sys import stdin

stdin = open('data/retire.txt')
input = stdin.readline
n = int(input())
consults = [tuple(map(int, input().split())) for _ in range(n)]

def solution(consults):
    ans, memo = 0, {}
    def dfs(i):
        if i in memo: return memo[i]
        if i >= len(consults): return 0
        Ti, Pi = consults[i]
        case1 = dfs(i + Ti) + Pi if i + Ti <= len(consults) else 0
        case2 = dfs(i + 1)
        memo[i] = max(case1, case2)
        return memo[i]
    ans = dfs(i=0)
    return ans

print(solution(consults))

55

Bottom Up

In [12]:

from sys import stdin
from collections import defaultdict 

stdin = open('data/retire.txt')
input = stdin.readline
n = int(input())
consults = [tuple(map(int, input().split())) for _ in range(n)]

def dynamic(consults):
    dp, n = defaultdict(int), len(consults)
    for i in range(n - 1, -1, -1):
        Ti, Pi = consults[i]
        if Ti + i > n:
            dp[i] = dp[i + 1]
        else:
            dp[i] = max(dp[i + 1], Pi + dp[i + Ti])
    return dp[0]

print(dynamic(consults))

55

Report

백준 제출시 체크 리스트

1. 런타임 에러
   • 제공하지 않은 library 사용했는가?
     
   • 정답 이외에 다른 것을 print했는가?
     
   • 인덱스를 초과 시키지 않았는가?
     
   • Space Complexity가 너무 높아 overflow된 것이 아닌가?
     
2. 시간 초과
   • 너무 naive한 알고리즘이 아닌가?
   • 비효율적으로 짠 부분이 있는가?
   • 재귀를 너무 많이 사용
   • 다른 etc 연산에 의한 overhead