[그리디 알고리즘] 2839번 설탕배달 풀이(파이썬)

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 백준에 제시된 문제 풀이와 스스로 얻은 정보를 정리하고자 합니다.

그러므로 단순히 문제를 푸는 것이 중요한 것이 아니라, 문제를 통해 얻어가는 것이 있어야하기 때문에 접근 방식은 이전 기초 300제를 풀었을 때랑 동일합니다.

 

[접근 방식]

- 문제에서 요구하는 역량은 무엇인지?

- 알고 있어야하는 지식은 무엇인지? 에 기반하여 풀이하고자 합니다.

 

- 백준 문제 링크입니다. : https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

---

[풀이 아이디어]

- 가장 적은 봉지 수를 구해야하므로, 최대한 5를 많이 활용할 수 있으면 좋을 것.

- 5를 가장 많이 활용하기 위해선 최대한 큰 수에서 5를 나눠야한다. 

- 그러기 위해선 N에서 뺄 수 있는 가장 작은 수인 3을 계속 빼가면서 5의 배수가 나올때 까지 찾을 것(ex. 18,21..)

- 만약 5의 배수가 안나온 상태로 N이 0이 된다면 그 상태로 종료(ex. 3,6,9,12)

- 나머지 1,2가 생긴다면 -1 출력

 

 

1. 그리디 알고리즘으로 풀이

N = int(input())
count = 0
# N이 5로 나누어지면 바로 출력
if N%5 == 0:
    print(N//5)
else:
    while True:
    # N에서 3씩 빼보기/뺄 때마다 카운트 개수 올려주기
        N=N-3
        count+= 1
    # 뺀 값이 5로 나눠지면 출력하고 break
        if N%5 == 0:
            print(count+N//5)
            break
        elif N < 3:
            print(-1)
            break
        else:
            continue

2달전에는 그리디로 위와 같이 풀었는데.. 관련 알고리즘에 DP도 있길래 오늘 DP로도 다시 풀어보았다.

사실 코드 구현이 그리 복잡한 문제는 아니어서 큰 차이는 없지만 연습삼아..

 

2. DP 로 풀이

import sys
input = sys.stdin.readline


n = int(input())
# N-3할때마다 값을 담아줄 bag 리스트 생성
bag = [n]
while True:
    # 3이하 남는 게 생기면 -1
    if 0< n < 3:
        print(-1)
        break
    # 5로 나누어 떨어지면 'bag 리스트 마지막에 담긴 수/5' + 'bag 리스트 요소 개수-1' 을 더해줄 것
    if n%5 == 0:
        print((bag[-1]//5)+(len(bag)-1))
        break
    elif n%5 !=0 and n>0 :
        n = n-3
        bag.append(n)
        continue

큰 차이는 없겠지만..이전보다 문제 해결을 위한 접근법이 다양해진 것 같다.

 

감사합니다.