백준 2839 설탕배달 - Python

브론즈이지만 정답비율이 33%로 낮은 문제이다.

DP가 기초단계라면 이 문제 추천한다!

Top-down / bottom-up 두 가지 방법으로 접근할 수 있다.

 

나는 브루트포스 / bottom-up 두 가지 방법으로 풀었고,

Top-down 으로 푸는 방법은 런타임 에러가 뜨는 상태이다..!

 

1. 브루트포스

N = int(input())


five_max = 5000//5
three_max = 5000//3
min_count = three_max
for i in range(three_max,-1,-1):
    total = 3*i
    if total == N and i < min_count:
        min_count = i
    else:
        for j in range(0,five_max+1):
            total = 5*j + 3*i
            if total == N and i + j < min_count:
                min_count = i+j
            elif total > N:
                break

    
print(min_count if min_count != three_max else -1)

 

 

 

2. bottom-up

N = int(input())
dp = [0xffffffff]* (N+5)

dp[0] = dp[1] = dp[2] = dp[4] = 0
dp[3] = 1
dp[5] = 1
for i in range(3, N):
    if dp[i]:
        dp[i + 3] = min(dp[i+3], dp[i]+1)    
        dp[i + 5] = min(dp[i+5], dp[i]+1) 

if dp[N] == 0 or dp[N] == 0xffffffff:
    print('-1')
else:
    print(dp[N])

 

시간차이가 굉장하다,,

 

 

3. Top-down

N = int(input())
dp = [0] * (N+6)
dp[0] = dp[1] = dp[2] = dp[4] = -1
dp[3] = dp[5] = 1
def topDown(N):
    if dp[N] == 0:
        if N-3>=0 and dp[N-3] == 0:
            a = topDown(N-3)
        else:
            a = dp[N-3]

        if N-5>=0 and dp[N-5] == 0:
            b = topDown(N-5)
        else:
            b = dp[N-5]
        if N == 4:
            print(b)
        dp[N-3] = a if a != -1 else 0xffffffff
        dp[N-5] = b if b != -1 else 0xffffffff

        dp[N] = min(dp[N-3]+1, dp[N-5]+1)
        return dp[N]
    elif dp[N] == -1:
        return -1
    else:
        return dp[N]

topDown(N)
if dp[N] == -1 or dp[N] == 0xffffffff + 1:
    print('-1')
else:
    print(dp[N])

n이 커질경우, RecursionError: maximum recursion depth exceeded in comparison

이런 에러가 뜬다..!