[백준/Python] 2839번: 설탕 배달

📁 문제

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


💭 첫 번째 풀이 (실패)

if n % 3 == 0:
  print("{}".format(n // 3))
elif n % 5 == 0:
  print("{}".format(n // 5))
  
else:
  if n < 5:
  
    if n % 3 == 0:
      print("{}".format(n // 3))
    else:
      print("-1")
      
  else:
    a = n // 5
    r = n % 5
    
    if r > 0:
      n = n - 5
      result = 1 # 5kg 1봉지 추가
    else:
      n = n - 10
      result = 2
      
    c = n // 3
    if n % 3 == 0:
      result += c
      print(result)
    else:
      print("-1")

나름 풀어보긴 했는데 엄청 난해하고 복잡하다... 역시 답도 틀리게 나온다... 좌절...
하지만 여기서 포기 못 해ㅠ 알고리즘 구상부터 다시 시작!


💭 두 번째 풀이 (실패)

조건문만 계속 사용하니까 코드도 복잡해지고 문제 풀기가 너무 힘들어서 + 변수명도 너무 헷갈려😵
이번에는 재귀함수를 사용해보았다.

def Sugar(n):
  r = 0

  n = n - 3
  r += 1

  if n == 1 or n == 2:
    return -1

  if n % 5 == 0:
    r += n // 5
    return r

  return Sugar(n)

어느 정도 되는 것 같아서 제출했는데 틀렸다고 나왔다😱

결과를 보니,
3의 배수와 같이 3kg 봉지가 여러 개 필요한 경우에 봉지의 개수가 누락되는 문제가 발생하였다.

문제가 발생하는 부분이 r을 초기화하는 부분인지 r에 값을 더하는 부분인지 모르겠다,,

이 부분은 좀 더 생각해 봐야겠다.


🤍 성공!

재귀 함수를 사용하니 문제가 도저히 풀리지 않아서 반복문을 사용하여 풀었더니 성공했다😄

코드가 훨씬 간단하고 가독성이 좋아졌다.

def Sugar(n):
  r = 0

  while(1):
    if n % 5 == 0:
      r += n // 5
      return r
      
    n = n - 3
    r += 1

    if n < 3 and n != 0:
      return -1
  • 5의 배수가 될 때까지 입력 값에서 3을 빼고 결과 값에 1을 더해주는 것을 반복한다.
  • 3을 뺐는데, 3 이하의 수가 나오면 정확하게 N킬로그램을 만들 수 없는 경우이므로 -1을 반환한다.
    • 단, 0인 경우는 정확하게 N킬로그램을 만들 수 있는 경우이므로 제외한다.
  • 5의 배수가 되면 결과 값에 5로 나눈 결과를 더한 후 그 값을 반환한다.

그리디 알고리즘 문제를 처음 풀어보는 거라서 많이 헤매기도 했지만, 풀고 나니 왜 그렇게 헤맸는지 모를 만큼 간단했다. 아마 풀기도 전에 겁부터 먹어서 그런 걸 지도? 내가 이때까지 얼마나 복잡하게 코드를 작성하고 있었는지 깨닫게 해 준 문제,, 이제 겁먹지 말자

좋은 웹페이지 즐겨찾기