백준 그리디 문제입니다. 알고리즘 숙달을 위한 문제 반복풀이입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 소요 시간 24분

N = int(input())

bongji3 = 1

while True:

    sugar = N

    if sugar%5==0:
        print(sugar//5)
        break

    sugar -= bongji3*3

    if sugar<0:
        print(-1)
        break

    if sugar%5 == 0:
        # print("5kg : ",sugar//5," , 3kg : ",bongji3)
        # print("총 갯수 : ",sugar//5+bongji3)
        print(sugar//5+bongji3)
        break
    bongji3 += 1

5kg 봉지와 3kg 봉지를 조합하여 모든 설탕을 최소 갯수의 봉지로 할당하는 문제입니다.

우선적으로 5kg 봉지만으로 해결이 가능할 때 break 하는 조건을 설정하였고 아니라면 3kg 봉지를 추가한 뒤 다시 필요한 5kg 봉지 갯수를 구하는 방식입니다.

5kg 봉지가 많을 수록 사용하는 봉지 갯수가 줄어드므로 3kg 봉지를 1개,2개,3개.. 씩 추가하는 것을 우선으로 조합을 찾는 것이 시간을 줄이는 포인트였습니다.

[다른사람의 풀이1]

sugar = int(input())

bag = 0
while sugar >= 0 :
    if sugar % 5 == 0 :  # 5의 배수이면
        bag += (sugar // 5)  # 5로 나눈 몫을 구해야 정수가 됨
        print(bag)
        break
    sugar -= 3  
    bag += 1  # 5의 배수가 될 때까지 설탕-3, 봉지+1
else :
    print(-1)

제가 구현한 방식과 유사한 풀이로 3kg 봉지를 1개씩 할당하며 5kg 봉지만으로 해결이 가능한지 판단하는 풀이입니다.

[다른사람의 풀이2]

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

저의 풀이와 유사하지만 다른 점은 조건문을 세부적으로 추가하므로서 약간의 시간을 줄인 풀이입니다.

저의 코드에 없는 조건, 남은 설탕 무게가 3 or 5로 나누 떨어지지 않으면서 1kg 혹은 2kg 일때는 3kg/5kg 봉지로 해결할 수 없으므로 바로 -1을 출력하는 조건을 추가한 풀이였습니다.

감사합니다.