[백준 2839] 설탕 배달

채점 결과

무려 5달 전 시도했다가 틀리고 방치했던 문제... 새로운 기법을 공부해 돌아왔다

---

제약 조건

문제

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

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

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

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

예제

예제

---

나의 풀이

n = int(input())
count = [-1] * 5001
count[3], count[5] = 1, 1
for i in range(n+1):
    if count[i] != -1:
        for num in (3, 5):
            if i+num > 5000: continue
            if count[i+num] == -1:
                count[i+num] = count[i] + 1
            else:
                count[i+num] = min(count[i+num], count[i] + 1)
print(count[n])

 

이런 유형을 DP라고 해야할 지 모르겠지만 DP의 풀이와 약간 계수 정렬의 느낌으로..? 풀이했다.

 

2021.08.22 - [백준 1463] 1로 만들기 (DP 문제)

[백준 1463] 1로 만들기 (DP 문제)

2021.08.21 - [Python] 계수 정렬 (Count sort)

[Python] 계수 정렬 (Count sort)

 

그림 설명

크기가 5001인 리스트 count를 생성 후 -1로 초기화 (그림에서는 17까지만 그림)

3과 5에 1을 저장

-1이 아닌 수를 만나면 +3과 +5를 확인. -1이라면 현재 인덱스 값에서 1을 더해서 저장

+3과 +5의 인덱스 값이 -1이 아니라면 현재 인덱스 값 + 1 과 발견된 숫자 중 더 작은 것을 선택해서 저장

현재 인덱스가 5이고, +3인 8번 값이 -1이 아니기 때문에 5번에 저장된 1+1과 8번에 저장된 값 중 더 작은 값을 저장한다. 여기서는 두 값이 동일하기 때문에 2를 저장한다. (3+5 == 5+3)

반복

이 경우 12번의 4 + 1과 (+3인)15번의 3이 다른 값이기 때문에 더 작은 3을 그대로 둔다.

+3이나 +5가 범위를 벗어나면 무시된다.

실제로 0~17까지 출력해보면 동일하게 만들어진 것을 알 수 있다.

리스트가 완성되었기 때문에 3~5000까지의 수 중 최소 개수를 알고 싶다면 그저 해당 인덱스의 값을 확인하면 끝이다.