211115 백준 코딩연습 파이썬 2839 설탕 배달

https://solved.ac/



파이썬

브1 설탕 배달

맞은 코드

def searchBongji():
    share = N // 5
    remain = N % 5
    if remain == 0:
        result = share
        return result
    share2 = remain // 3
    remain2 = remain % 3
    if remain2 == 0:
        result = share + share2
        return result
    while(True):
        if share:
            share -= 1
        temp = share * 5
        share2 = (N - temp) // 3
        remain2 = (N - temp) % 3
        if remain2 == 0:
            result = share + share2
            return result
        if share <= 0 or share2 == 0:
            return -1
N = int(input())
result = 0
print(searchBongji())

딱 봤을 때 그리디 알고리즘인 것 같았는데 생각보다 푸는데 힘들었다.

봉지의 최소 개수를 구해야하므로 5킬로그램을 우선으로 생각하고 풀었다.

젤 처음에 N개에서 5로 모듈러 연산을 해서 5의 배수인지 보고 아니면 나머지를 3으로 모듈러 연산을 해서 나머지가 3의 배수인지 확인한다.

만약 거기서 계산이 끝나지 않으면 여기서부터 무한루프를 돌린다.

5의 몫을 1씩 줄이면서 나머지가 3으로 나누어떨어질때까지 혹은 5의 몫이 0 이하거나 3의 몫이 0이 될 때까지 루프가 반복된다.

아무튼 풀다보니 이렇게 풀었는데 옳은 방법이었는지는 잘 모르겠다.

같이 코테 스터디를 하는 친구는 조금 다른 방법으로 풀었다.

코테 스터디원 코드

A = int(input())
cnt = 0
while(1):
    if A % 5 == 0:
        A = A-5
        cnt +=1
    elif A % 3 == 0:
        A = A -3
        cnt +=1
    else:
        A = A-3
        cnt += 1
    if A ==0:
        break
    if A<0:
        cnt = -1
        break
print(cnt)

나와 비슷하게 5를 우선순위로 했고

나누어떨어지면 1씩 카운트하는 것을 N이 0 이하가 될 때까지 무한루프를 돌린다.

이게 내 코드보다 훨씬 이해하기에도 편하고 직관적으로 잘 짠 듯 싶다.

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

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

지금은 이 문제도 버겁게 풀었지만 나중에는 위 두 문제처럼 어려운 그리디 알고리즘도 잘 풀어보고 싶다.