[백준] 2839번: 설탕 배달 (파이썬)

 

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

 

▶ 문제 탐색하기

전체 설탕의 양인 N을 3a + 5b 로 풀어내어서 (a+b)의 최솟값을 구하는 문제로 생각했다. 몫이 상대적으로 작은 a값을 중심으로 이중 for문을 이용해서 풀었다. 

 이중 for 문(아래)을 사용해 푼 문제가 while~else로 푼 문제(위)보다 시간이 엄청 오래걸렸다. O(nm) 시간 복잡도가 크긴 하다.

 

▶ 정답 코드 (이중 for 문)

N = int(input())
a = N // 5    # 5의 최대 몫
b = N // 3    # 3의 최대 몫
w = []        # 5a + 3b = 15가 가능한 (a+b)의 배열
for i in range(a+1):
    for j in range(b+1):
        if (5 * i) + (3 * j) == N:
            w.append(i+j)        
if w:
    print(min(w))  # 최소 (a+b) 값 찾기
else:
    print('-1')

▶ 추가 풀이

찾아보니까 대부분은 이렇게 풀었다. 어떻게 이런 생각을 처음부터 할 수 있는거지?

while~break 쓰는 연습이 부족한거같다.

sugar = int(input())

bag = 0
while sugar >= 0 :
    if sugar % 5 == 0 :  
        bag += (sugar // 5)  
        print(bag)
        break
    sugar -= 3  
    bag += 1  
else :
    print(-1)