[백준] 2839. 설탕 배달 (Python)

백준 문제 풀이 - 다이나믹 프로그래밍

📰 문제

---

문제 확인 🏃

💡 입출력 예제

---

18

>> 4

4

>> -1

6

>> 2

9

>> 3

11

>> 3

💬 풀이

---

🎵 첫번째 풀이 - DP

N = int(input())        # 배달해야 하는 설탕 무게

def solution():

    table = [0, 0, 0, 1, 0, 1]   # 0, 1, 2, 3, 4, 5

    for idx in range(6, N+1):

        table.append(table[idx-3] + 1 if table[idx-3] else 0)           # 3
        temp = table[idx-5] + 1 if table[idx-5] else 0                  # 5

        if table[idx] and temp:
            table[idx] = min(temp, table[idx])
        elif not table[idx]:
            table[idx] = temp

    return table[N]

print(-1 if not solution() else solution())

더 예쁘게 풀 수는 없을까?

🎵 두번째 풀이 - DP

N = int(input())        # 배달해야 하는 설탕 무게

def solution():

    table = [float('inf') for _ in range(6)]   # 0, 1, 2, 3, 4, 5
    table[3], table[5] = 1, 1

    for idx in range(6, N+1):
        table.append(min(table[idx-3], table[idx-5]) + 1)

    return -1 if table[N] == float('inf') else table[N]

print(solution())

🎵 세번째 풀이 - DP

N = int(input())        # 배달해야 하는 설탕 무게

def solution():

    table = [0, 0, 0, 1, 0, 1]   # 0, 1, 2, 3, 4, 5

    for idx in range(6, N+1):

        table.append(table[idx-3] + 1 if table[idx-3] else 0)           # 3
        temp = table[idx-5] + 1 if table[idx-5] else 0                  # 5

        if temp:
            if table[idx]: table[idx] = min(temp, table[idx])
            else: table[idx] = temp

    return table[N] if table[N] else -1

print(solution())

🎵 네번째 풀이 - 수학

N = int(input())        # 배달해야 하는 설탕 무게

def solution(N):
    answer = 0

    while N >= 3:
        if N % 5 == 0:
            answer += (N//5)
            N %= 5
        else:
            answer += 1
            N -= 3

    return -1 if N else answer

print(solution(N))

✒️ 생각

---