22.10.21/ DP

2839 설탕 배달

나의 풀이

알고리즘 - Dynamic Programming(동적 계획법) (tistory.com)

DP 사용 조건
1. 동일한 작은 문제들이 반복 (부분 문제 존재)
2. 부분 문제에서 얻은 값이 가장 최적의 값

특정 데이터 내 최대화 / 최소화 계산
특정 조건 내 데이터를 세야함
확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.

1. DP 문제인지 파악
2. 변수 파악
3. 관계식 만들기 (점화식)
4. 변수 값 저장 (Memoization. 보통 배열 사용)
5. 기저 상태 정의 (가장 낮은 최후 값)
6. 구현 (Bottom-Up 반복문 or Top-Down 재귀문)

Bottom-Up :
반복문 구현- 아래(기저)에서 누적시켜 전체 큰 문제 해결. 
Top-Down :
재귀문 구현- n에서 출발하여 기저상태까지 재귀 수행.

'''
# N의 최대값은 5000
dp_kg = [0] * 5000

def dp(n_kg):
    # N의 값은 N-3이나 N-5에서 얻어진다. 재귀적으로 탐색
    # dp(N)의 값은 더 적은 값을 선택한다.
    if n_kg == 0:
        return 0
    elif n_kg < 0:
        return 9999
    dp_kg[n_kg] = min(dp(n_kg-3) +1, dp(n_kg-5) +1)
    return dp_kg[n_kg]
#재귀 회수 증가로 인한 RecursionError 발생
'''

def dp(n_kg):
    dp_kg = [9999] * 5005
    dp_kg[3], dp_kg[5] = 1, 1
    
    # 반복문은 Bottom-up 형태로 풀이한다.
    for i in range(3, n_kg):
        if(dp_kg[i] != -1):
            # 이미 작성된 값 중, 더 적은 값이 있으면 그 값 선택.
            dp_kg[i+3] = min(dp_kg[i+3] , dp_kg[i] +1)
            dp_kg[i+5] = min(dp_kg[i+5] , dp_kg[i] +1)
    
    if(dp_kg[n_kg] == 9999):
        return -1
    return dp_kg[n_kg]

n_kg = int(input())
# 파이썬에서는 자료형 캐스트를 잊지 말고 해주자.
n = int(dp(n_kg))
print(n)

성공한 풀이이다.

하지만 다른 풀이는 N-a식으로 접근한다. 나같은 경우 N+a식으로 작성했다.

이것도 값을 재사용하는 DP라고 생각하지만, N-a식으로 작성하는게 더 보편적이지 않을까 싶다.

 

더 나은 풀이

백준 2839 파이썬 - 설탕 배달 - 동적 계획법 (tistory.com)

작성해주신 위의 블로그를 참고하여 N-a 형태의 식으로 바꾸어 작성해보았다.

def dp_other(n_kg):
    dp_kg = [9999] * 5001
    dp_kg[3] = dp_kg[5] = 1
    
    for i in range(6, n_kg+1):
        dp_kg[i] = min(dp_kg[i-3], dp_kg[i-5]) +1
        
    if(dp_kg[n_kg] >= 9999):
        return -1
    return dp_kg[n_kg]

print(dp_other(int(input())))

min을 쓰기위해 5001이라는 큰 수로 초기화했다.

3, 5에 해당되는 값만 정상적으로 Bottom-Up되고, 그렇지 않은 값은 5001이 넘는 값으로 작성된다.

A if 조건식 else B라는 한줄 if문도 사용했다.

 

리뷰

DP를 사용할 때와 어떻게 작성할지(Top-Down, Bottom-Up)를 알아두자.
파이썬은 최대재귀깊이(1000번)이 있으므로 Bottom-Up방식을 사용해야만 한다.
DP배열은 초기값이 존재해야 되고, 값을 재사용할 수 있도록 설계하도록 한다.