백준 - 2839번 설탕배달 python 문제풀이 [Hellfer]

 

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

2839번: 설탕 배달

🔷 알고리즘 분류 - 다이내믹프로그래밍, 그리디 알고리즘, 난이도 - 실버 4

다이내믹 프로그래밍(Dynamic Programming, DP)은 크게 '중복되는 부분 문제', '최적 부분 구조' 두 가지 특성을 가진 문제에 적용되는 알고리즘 설계 기법입니다.

중복되는 부분 문제(Overlapping Subproblems): 이는 주어진 문제가 같은 문제를 여러 번 반복해야 하는 경우를 의미합니다. 

 

예를 들어, 피보나치수열에서 피보나치 수를 구할 때, 각 수는 이전 두 개의 피보나치 수의 합으로 표현되는데, 이때 같은 수를 반복해서 구하게 되는 상황이 발생합니다.

최적 부분 구조(Optimal Substructure): 큰 문제의 최적 해결 방법이 작은 문제들의 최적 해결 방법으로부터 구해질 수 있는 경우를 의미합니다.

 

예를 들어, 가장 긴 증가하는 부분 수 (Longest Increasing Subsequence, LIS) 문제에서, 전체 수열의 LIS를 구하기 위해서는 부분 수열들의 LIS를 먼저 구해야 합니다.

이런 특성을 만족하는 문제에 대해 DP를 적용하면, 먼저 작은 문제들의 해를 구하고 이를 이용해서 큰 문제의 해를 구하는 방식으로 문제를 효율적으로 해결할 수 있습니다. 

 

이 과정에서 계산 결과를 저장해 두었다가 필요할 때 불러와 사용하는 메모이제이션(Memoization) 기법을 사용하면, 중복된 계산을 줄이고 시간 복잡도를 개선하는 데에 도움이 됩니다.

다이내믹 프로그래밍은 계산 복잡성이 큰 문제를 효과적으로 해결할 수 있게 해주는 강력한 도구입니다. 

 

하지만, 다이내믹 프로그래밍으로 해결 가능한 문제는 해당 특성을 만족하는 문제에 한정되며, 문제를 어떻게 나눌 것인지, 작은 문제의 해를 어떻게 큰 문제의 해로 확장할 것인지에 대한 이해가 필요합니다.

 

그리디 알고리즘(Greedy Algorithm)은 매 순간 최적이라고 생각되는 결정을 하는 방식으로 문제를 해결하는 알고리즘입니다. 

 

이 때문에 그리디 알고리즘은 '탐욕적'이라는 뜻의 '그리디'라는 이름이 붙었습니다.

그리디 알고리즘이 작동하는 기본 원리는 간단합니다. 매 순간 최선의 선택을 하면서 전체 문제의 해결책을 찾아나갑니다. 

 

이 때문에 그리디 알고리즘은 많은 종류의 최적화 문제에 효율적으로 사용될 수 있습니다.

그러나 그리디 알고리즘은 '항상 최적의 해결책을 보장하는가?'라는 중요한 질문에 대한 답이 '아니요'일 수 있다는 점에서 주의할 필요가 있습니다. 

 

그리디 알고리즘은 그 자체로 국소적인 최적해를 찾는 데는 탁월하지만, 이가 반드시 전체적인 최적해를 보장하진 않습니다.

🔶첫 번째 풀이 - 그리디 알고리즘을 이용한 풀이

N = int(input())
bag = 0

while N >= 0 :
    if N % 5 == 0 :  # 5로 나누어 떨어지면
        bag += (N // 5)  # 5로 나눈 몫을 봉지 개수에 추가
        print(bag)
        break
    N -= 3  # 5의 배수가 될 때까지 설탕 무게에서 3을 빼줌
    bag += 1  # 3킬로그램 봉지 추가
else :
    print(-1)

🔶두 번째 풀이 - 반복문을 이용한 풀이

N = int(input())

if N == 4 or N == 7:    # 4kg, 7kg은 3kg과 5kg으로 정확히 만들 수 없는 무게이므로 -1 출력
    print(-1)
elif N % 5 == 0:        # N이 5의 배수이면, 5kg 봉지만으로 모두 담을 수 있으므로 N/5 출력
    print(N // 5)
elif N % 5 == 1 or N % 5 == 3: # N이 5로 나눴을 때 나머지가 1이거나 3이면, (N//5)+1 출력
    print(N // 5 + 1)
else:                   # N이 5로 나눴을 때 나머지가 2이거나 4이면, (N//5)+2 출력
    print(N // 5 + 2)

🔶 초보자를 위한 해결전략

이 문제는 설탕을 정확히 N킬로그램을 배달하는데, 설탕은 3킬로그램 봉지와 5킬로그램 봉지가 있습니다. 

이때, 배달하는 봉지의 최소 개수를 구하는 문제입니다.

이 문제는 그리디 알고리즘을 이용해 해결할 수 있습니다. 먼저, 설탕의 총무게를 5로 나누어 보고, 나누어 떨어지면 이를 바로 결과로 출력합니다. 만약 나누어 떨어지지 않는다면, 3킬로그램 봉지를 하나씩 추가하면서 다시 5로 나누어 보는 과정을 반복합니다. 

이렇게 5킬로그램 봉지를 최대한 많이 사용하되, 나머지는 3킬로그램 봉지로 채우는 방식으로 최소의 봉지를 구합니다.

하지만, 3킬로그램과 5킬로그램을 사용하여 정확히 N킬로그램을 만들 수 없는 경우도 있으므로, 이 경우에는 -1을 출력합니다. 이러한 경우는 주로 N이 3과 5로 나누어 떨어지지 않는 경우에 발생합니다.

이처럼 문제를 해결하는데 필요한 로직을 구현하면, 설탕 배달 문제를 해결할 수 있습니다.

 

🤗파이팅입니다~ 여러분!!🤗