[백준_python] 설탕 배달 || 2839 ( 동적 계획법, 그리디 알고리즘, 런타임 에러(RecursionError))

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

이전 풀이

https://dmaolon00.tistory.com/18

[백준_python] 설탕 배달 || 2839

---

이전 풀이에서 두 번째 풀이와 마찬가지로 풀이를 해주었다.
5로 나누어 떨어지지 않는다면 3을 빼주며, 5로 나누어떨어지면 몫만큼 횟수를 세어주었다. 음수가 되면 -1을 출력되도록 해주었다.
 
이전에 풀이해둔 것과 거의 동일하기 때문에 포스팅을 안하려고 그랬는데 알고리즘 유형을 확인해보니, 그리디 알고리즘과 다이나믹 프로그래밍을 이용할 수 있는 문제라고 한다.
 

▷ 그리디 알고리즘

 
이번에 풀어보면서 아래의 문제와 흡사하게 풀어주면 되겠다라며 생각했었고,

2021.07.05 - [문제 풀이/AGAIN] - [백준_python] 동전 0 || 11047

[백준_python] 동전 0 || 11047

 

내가 사용한 알고리즘은 그리디 알고리즘이다.
미래를 고려하지 않고 지금 고르는 선택이 가장 최선의 선택이길 바라는 기법이다. 따라서 주어진 조건에 따라 항상 최선의 결과가 나온다는 보장이 없다. 그렇지만 빠르게 최적해를 찾아낼 수 있다.
 

n = int(input())
cnt = 0

while True:
    if n % 5 != 0:
        n = n - 3
        cnt += 1

    elif n % 5 == 0:
        cnt += n // 5
        print(cnt)
        break

    if n < 0:
        print(-1)
        break

---

▷ 동적 계획법

 
동적 계획법, 다이나믹 프로그래밍, DP로는 어떻게 풀이해줄 수 있을까..?
Dynamic Programming이란 큰 문제를 작은 문제로 나누어 푸는 문제로, 작은 부분 문제들이 반복된다.
(분할 정복은 작은 부분 문제들이 반복되지 않는다.[차이점])

 

1	2	3	4	5	6	7	8	9	10
-1	-1	1	-1	1	2	-1	2	3	2
x	x	3 x 1	x	5 x 1	3 x 2	x	3 + 5	3 x 3	5 x 2

 

11	12	13	14	15	16	17	18	19	20
3	4	3	4	3	4	5	4	5	4
5 + 3 x 2	3 x 4	5 x 2 + 3	5 + 3 x 3	5 x 3	3 x 2 + 5 x 2	3 x 4 +5	3 + 5 x 3	3 x 3 + 5 x 2	5 x 4

 

예를 들어 15를 살펴보자면,
15는 3 x 5가 될 수도 있고, 5 x 3이 될 수도 있다.
3 x 5는 12( 15 - 3 )의 값에서 3을 추가하며 구할 수 있다.
5 x 3은 10( 15 - 5 )의 값에서 5를 추가하여 구할 수 있다.
 
점화식은 dp[n] = 1 + min( dp[n-3] , dp[n-5] ) 가 된다.
 

def dynamic(n):
    if n < 3 or n == 4 or n == 7:
        return dp[n]

    elif n == 3 or n == 5:
        dp[n] = 1
        return dp[n]

    if dynamic(n-3) < 0 or dynamic(n-5) < 0:
        return 1 + max(dynamic(n-3), dynamic(n-5))

    return 1 + min(dynamic(n-3), dynamic(n-5))


x = int(input())
dp = [-1] * (x + 1)
print(dynamic(x))

입력받은 수가 3보다 작거나, 4, 7인 경우에는 -1이 리턴되도록, 3과 5일 경우에는 1이 리턴되도록 하였다.
그리고 n - 3과 n - 5에서의 값이 -1인 경우에는 min으로 계산되면 안되기 때문에 max로 처리해주었다.
 
재귀함수를 이용하여 결과값이 제대로 나오긴 했으나, 백준에 제출하니 런타임 에러(RecursionError)가 발생했다.
 
https://www.acmicpc.net/help/rte/RecursionError

런타임 에러 도움말 (RecursionError)

최대 재귀 깊이를 초과하여서 생긴 오류라고 한다.
이를 해결해주기 위해서는 재귀 함수를 이용하지 않거나, 

import sys
sys.setrecursionlimit(10**6)

를 추가해주어 최대 재귀 깊이를 설정해주는 것이라고 한다.
 
최대 재귀 깊이를 설정해주어도 pypy3으로 제출을 해봐도 시간 초과가 발생하여 결국 재귀함수를 이용하는 것 대신
반복문을 사용해주기로 했다..ㅠ

 

x = int(input())
dp = [-1] * (x + 1)

if x >= 3:
    dp[3] = 1
if x >= 5:
    dp[5] = 1

for i in range(6, x + 1):
    if dp[i - 3] < 0 and dp[i - 5] < 0:
        dp[i] = -1

    elif dp[i - 3] > 0 and dp[i - 5] > 0:
        dp[i] = 1 + min(dp[i - 3], dp[i - 5])

    else:
        dp[i] = 1 + max(dp[i - 3], dp[i - 5])

print(dp[x])

dp를 미리 어느정도 지정해두면, dp[3] = dp[5] = 1로 해줄 수 있지만, 입력받은만큼만 배열이 생성되도록 해주었기 때문에 if문 두 개를 넣어주었다.
 
그 후 6부터 for문을 통해 반복문을 돌도록 하였다. 7일 경우에는 -1이 나와야 하는데, dp[4]와 dp[2]가 모두 -1이므로 결과값이 0이 되어버렸다. 따라서 위와 같이 조건을 3개로 나누어 만들어주었다.
뭔가 마음에 들지는 않지만,,,ㅎ
 
 
참고한 사이트!

https://velog.io/@hye0n/BOJPython-2839.%EC%84%A4%ED%83%95-%EB%B0%B0%EB%8B%AC

[BOJ/Python] 2839.설탕 배달