백준 그리디 문제풀이 입니다.

문제

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

[나의 풀이]

N = int(input())

ans = [-1]
bag = [5, 3]

# 가방 최대 갯수
max = N // bag[-1]

if N % bag[-1] != 0:
    max += 1

# 가방 최소 갯수 찾기
for i in range(max + 1):
    for j in range(max + 1):
        if N - bag[0] * i - bag[1] * j == 0:
            ans.append(i + j)
            # print(i, j, "체크")
            # print(bag[0] * i, bag[1] * j)
            del ans[0]

print(min(ans))

먼저 최악의 상황에서 사용해야하는 봉지의 갯수(max)를 구한 뒤 5kg 봉지, 3kg 봉지 각각 0부터 최대 갯수만큼 확인하여 최소로 필요하는 봉지의 갯수를 구하였습니다.🐬🐬🐬

저의 풀이 이외에 아래와 같이

[다른 사람의 풀이]

n = int(input())

if n % 5 == 0:  # 5으로 나눠떨어질 때
    print(n // 5)
else:
    p = 0
    while n > 0:
        n -= 3
        p += 1
        if n % 5 == 0:  # 3kg과 5kg를 조합해서 담을 수 있을 때
            p += n // 5
            print(p)
            break
        elif n == 1 or n == 2:  # 설탕 봉지만으로 나눌 수 없을 때
            print(-1)
            break
        elif n == 0:  # 3으로 나눠떨어질 때
            print(p)
            break

5kg 봉지로 나누어떨어질 때, 5kg or 3kg 봉지로 나누어떨어질 때, 3kg봉지로만 나누어떨어질 때, 나누어떨어지지 않을 때 경우의 수를 나누어 해결한 풀이를 볼 수 있었습니다.🐵🐵🐵

감사합니다.