[그리디 11] 설탕 배달

최적의 일반화

정답 비율 : 35.885%

1. 문제 설명하기.

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

일단 이 문제는 그리디 문제이다. 최대한 적은 횟수로 봉지를 가져가는 것이기 때문에 가장 좋은 것부터 선택하는 탐욕법을 이용하면 되기 때문이다. 하지만 나는 3부터 고려하여 문제를 풀었다. 구글링으로 최적의 코드를 보니, 5부터 고려하였고 내 코드보다 훨씬 간결하였다. 다음에는 5부터 고려하는 방식을 이용할 것이다.

2. 문제 해결하기.

삽질을 굉장히 많이 한 문제이다.

3일 내내 삽질하였다. 하나를 해결하면 다른 하나가 해결이 안되는 문제가 계속 발생하여 많은 예제를 통하여 일반화를 하였다.

조건 ①, ②, ③을 찾을 수 있었다. 조건 ②의 5의 배수는 조건 ③에서 고려하기 때문에 빼도 좋다.

N=int(input())

def delivery_sugar(N):
    # 5 이하인 수들 구현하기.
    count=0
    iter=1
    
    # 조건 ②
    if (N==1) or (N==2) or (N==4):
        return -1
    if (N==3):
        return 1
    
    # 조건 ③
    # 5의 배수들 구현하기.
    if N%5==0:
        count=N//5
        return count
    
    # 조건 ①
    # 제일 복잡한 부분 구현하기.
    while True:
        remaining=N-3*iter # iter : 3의 횟수
        if (remaining%5!=0) and (remaining>=3): 
        # 5의 배수가 아니면서, 3보다 큰 경우
            iter+=1
            continue # 계속 무한 반복문 진행하기.
        if (remaining%5!=0) and (remaining<3):
        # 5의 배수도 아니면서 3보다 작은 경우
            return -1 # 더 이상 진행 불가니 -1 리턴하기.
        count+=(iter+(remaining//5))
        # 3의 횟수 + 나머지를 5로 나눈 몫 = 전체 횟수
        return count
        
delivery_sugar(N)

주의 : 반드시 풀이를 제출할 때에 print() 해주기!! 위의 함수는 return만 진행하기 때문에, print()를 사용해야 제대로 된 답을 얻을 수 있다.

## 내가 만든 함수에서는 return 밖에 없기 때문에, 반드시 print()를 이용하여 답을 출력해야 한다.
## 요즘 사용자 함수 만드는 것을 연습하고 있는데, 다른 문제에서는 이런 실수를 반복하지 말자!

N=int(input())

def delivery_sugar(N):
    # 5 이하인 수들 구현하기.
    count=0
    iter=1
    
    # 조건 ②
    if (N==1) or (N==2) or (N==4):
        return -1
    if N==3:
        return 1
    
    # 조건 ③
    # 5의 배수들 구현하기.
    if N%5==0:
        count=N//5
        return count
    
    # 조건 ①
    # 제일 복잡한 부분 구현하기.
    while True:
        remaining=N-3*iter # iter : 3의 횟수
        if (remaining%5!=0) and (remaining>=3): 
        # 5의 배수가 아니면서, 3보다 큰 경우
            iter+=1
            continue # 계속 무한 반복문 진행하기.
        if (remaining%5!=0) and (remaining<3):
        # 5의 배수도 아니면서 3보다 작은 경우
            return -1 # 더 이상 진행 불가니 -1 리턴하기.
        count+=(iter+(remaining//5))
        # 3의 횟수 + 나머지를 5로 나눈 몫 = 전체 횟수
        return count
        
print(delivery_sugar(N)) # 드디어 성공!

이 풀이도 가능하다.

## 내가 만든 함수에서는 return 밖에 없기 때문에, 반드시 print()를 이용하여 답을 출력해야 한다.
## 요즘 사용자 함수 만드는 것을 연습하고 있는데, 다른 문제에서는 이런 실수를 반복하지 말자!

N=int(input())

def delivery_sugar(N):
    # 5 이하인 수들 구현하기.
    count=0
    iter=1
    
    # 조건 ②
    if (N==1) or (N==2) or (N==4):
        return -1
    if (N==3):
        return 1
    
    # 조건 ③
    # 5의 배수들 구현하기.
    if N%5==0:
        count=N//5
        return count
    
    # 조건 ①
    # 제일 복잡한 부분 구현하기.
    while True:
        remaining=N-3*iter # iter : 3의 횟수
        if (remaining%5!=0) and (remaining>=3): 
        # 5의 배수가 아니면서, 3보다 큰 경우
            iter+=1
            continue # 계속 무한 반복문 진행하기.
        if remaining<3:
        # 3보다 작은 경우
            return -1 # 더 이상 진행 불가니 -1 리턴하기.
        count+=(iter+(remaining//5))
        # 3의 횟수 + 나머지를 5로 나눈 몫 = 전체 횟수
        return count
        
print(delivery_sugar(N)) # 드디어 성공!

3. 구글링을 통해 얻은 최적의 일반화

가장 큰 수인 5부터 고려하는 방법이다. 이렇게 하면 5의 배수를 따로 고려하지 않아도 된다.

n = int(input())
count = 0

while True:
    if (n % 5) == 0: # 5의 배수인 경우
        count = count + (n//5)
        print(count)
        break
    n = n-3 # 5의 배수가 아니면 3을 빼고 다시 5의 배수인지 고려해보기.
    count += 1 # 3의 횟수가 늘었으니, +1 처리하기.
    if n < 0: # 0보다 작아지는 경우 사용 불가능하니, -1 출력하기.
        print("-1")
        break

Step 1. 5의 배수인지 확인하기. 맞다면 그 만큼 더해주고 무한 반복문을 종료한다.
Step 2. 5의 배수가 아니라면, 3을 빼고 5의 배수인지 확인해보기. 이 때 3의 횟수가 +1 되었으니 +1 처리를 해야 한다.
Step 3. 계속 위의 과정을 반복하다가 음수가 되는 경우, -1을 출력한다. 그리고 무한 반복문을 종료한다.

깔끔한 그리디 문제 풀이인 듯 하다.