[그리디 알고리즘] ▲ 2839번 - 설탕 배달

[백준] 2839번 - 설탕 배달

(풀이1) 내 풀이

1) 문제 해결 아이디어

복잡하게 소스코드를 작성하다가 한 순간 아이디어가 떠올라 수학적으로 접근하여 문제를 해결하였다.

 

3x + 5y =  n 이라는 식을 도출했다.

x, y가 모두 양의 정수인 (x, y)쌍을 찾고 그들 중에서 (x+ y)의 최소값이 정답이다.

물론 여기서 위의 조건을 만족하는 (x, y)가 없다면 이는 3, 5 봉지 종류로는 만들 수 없다는 뜻이므로 -1을 출력시켜야 한다.

 

x = 0부터 1씩 증가시키고 y는 x 값을 넣어 계산한 후, 

y가 음수가 되면 반복문을 탈출한다.

x, y는 모두 양수여야 하며 y가 float형으로 계산된다면 해당 x, y 쌍을 더한 값은 리스트에 넣지 않는다.

 

2) 소스코드

n = int(input())  # 설탕 무게
arr=[]	# 경우의 수

x = 0
while True:
  y = (n - 3  * x) / 5
  # 탈출 조건
  if(y < 0):
    break
  # 정수이면
  if(y == int(y)):
    arr.append(x + int(y))
  x += 1  

# 경우의 수가 없는 경우
if(len(arr) == 0):
  print(-1)
else:
  print(min(arr))	# 최소값 출력

 

(풀이2) 참고 풀이

 

1) 문제 해결 아이디어

.내가 떠올린 풀이와 비슷한 방식이긴 하지만 다르게 구현한 코드이다.

필요한 최소 봉지 수를 계산하기 위해 무게가 5의 배수가 아닐 때까지 3을 빼고 봉지수를 추가하는 방식이다.

 

2) 소스코드

n = int(input())  # 설탕 무게
res = 0  # 봉지 수

while n >= 0:
  # 5의 배수이면
  if(n % 5 == 0):
    res += n // 5  # 봉지 수 추가
    print(res)  
    break
  n -= 3  # 5의 배수가 될 때까지 반복
  res += 1  # 봉지 수 추가
# while 문이 False이면(n이 음수가 되면)
else:
  print(-1)

<while ~ else 문>

while 조건식:     실행문1 else:     실행문2

조건식이 True이면 실행문1을 반복 실행하고 조건식이 False가 되면 while문을 탈출하여 else문 실행 만약 break에 의해 while문을 탈출하면 else문은 실행되지 않는다.