[백준]2839번: 설탕 배달

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

2839번: 설탕 배달

---

아이디어

1. 5kg봉지에 설탕을 담을 수 있는 만큼 담는다.

2. 남은 설탕의 양이 3kg으로 나누어떨어져야만 3kg 봉지에 담아서 배달이 가능하다.

    따라서 남은 설탕의 양이 3으로 나누어떨어지지 않으면, 5kg봉지로부터 다시 설탕을 붓는다. (되돌리기)

 

3-1. 남은 설탕의 양이 3kg으로 나누어떨어지게 되는 순간이 오면, 남은 설탕을 3kg 봉지에 모두 나눠 담는다.

3-2. 모든 설탕을 다 부어도 3kg으로 나누어떨어지지 않게 되면 -1을 출력한다.

 

제출코드 (python)

n = int(input())

answer = 0

# 5kg짜리 봉지에 담기
if n//5 > 0:
  answer += n//5
  n %= 5

# 남은 설탕의 양이 3으로 나누어떨어지도록 조정하기
while n%3 != 0 and answer > 0:
  answer -= 1
  n += 5

# 3kg짜리 봉지에 담기
if n//3 > 0:
  answer += n//3
  n %= 3

# 결과 출력
if n > 0:
  print(-1)
else:
  print(answer)

 

다른 사람들 풀이

내 풀이가 좀 웃긴 것 같기도 해서 다른 사람들 코드 여러 개를 구경해보았다.

 

✅ 그리디 방법으로 푼 사람들이 가장 많았다.

n을 5로 나눈다 - 5로 나누어떨어지지 않으면 총 무게에서 3을 빼준다 - 총 무게가 0보다 작거나 같아지면 루프를 탈출 - 결과 출력

 

✅ 또, 나는 dp는 생각하지 못했는데 dp로 푼 사람들도 꽤 많았다.

1, 2, 3, 4, 5kg을 만드는 최소 봉지수는 각각 0, 0, 1, 0, 1 (0은 만들 수 없다는 뜻) 이다.

dp배열을 이렇게 초기화시켜놓고,

6부터 시작해서 Nkg을 만드는 최소 봉지수를 bottom-up 방식으로 계산해나가는 방법이었다.