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

📝 Problem

문제

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

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

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

입력

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

출력

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

예제 입력 1

18

예제 출력 1

4

예제 입력 2

4

예제 출력 2

-1

✅ Submit

세 가지 풀이가 있다.

1. top-down 방식의 DP (재귀사용)
2. bottom-up 방식의 DP (반복문사용)
3. 그리디

👌 Solved Code 1 : DP (top-down)

💡 Idea

표를 그려가면서 규칙성을 알아보고자 했다.

주요 로직은 다음과 같다.

1. 5의 배수인지 먼저 검사 → 맞다면, dp(n-5) 의 값에 1을 더한 값이 정답
2. 그 다음 3의 배수인지 검사 → 맞다면, dp(n-3) 의 값에 1을 더한 값이 정답
3. 1,2번을 둘 다 통과하지 못했다면 dp(n-5) 와 dp(n-3) 값 중 더 작은 값에 1을 더한 값이 정답.
   이 때, dp(n-5) 와 dp(n-3) 은 둘 다 양수여야 한다. (즉, 배달할 수 있는 경우여야 한다.)
4. 1,2,3 조건에서 걸러지지 못했다면, dp(n-5) 와 dp(n-3) 이 둘 다 -1 이라는 뜻이므로 dp(n) 도 -1 이다. (배달할 수 없다.)

💻 Code

# 재귀를 이용한 DP (top-down)

import sys

n = int(sys.stdin.readline())

def dp(n):
    cache[3] = cache[5] = 1
    cache[1] = cache[2] = cache[4] = -1

    if n not in cache:
        if n % 5 == 0:
            cache[n] = dp(n - 5) + 1
        elif n % 3 == 0:
            cache[n] = dp(n - 3) + 1
        elif dp(n - 5) > 0 and dp(n - 3) > 0:
            cache[n] = min(dp(n - 5), dp(n - 3)) + 1
        else:
            cache[n] = -1

    return cache[n]

cache = {}
print(dp(n))

💬 Commentary

맨 처음 풀었던 방식이다.

재귀를 이용하다보니 메모리를 많이 잡아먹고 결정적으로 파이썬은 내부적으로 재귀호출 횟수에 제한이 걸려있다보니, 썩 좋은 코드는 아닌 것 같다.

게다가 Python3 로 제출하면 재귀호출 횟수 제한 때문에 런타임 에러가 발생한다.

sys.setrecursionlimit(limit_number) 을 통해 재귀호출 제한을 풀거나, PyPy3 로 제출하면 정답처리가 되긴 한다.

👌 Solved Code 2 : DP (bottom-up)

💡 Idea

첫 번째 풀이코드랑 로직은 완전히 동일하다.

다만, 재귀를 사용하지 않고 반복문과 memoization 을 이용한 DP 로 풀었기 때문에 메모리와 실행시간 측면에서 훨씬 효율적이다.

💻 Code

# for문을 이용한 dp (bottom-up)

import sys

n = int(sys.stdin.readline())

dp = [-1] * 5001

dp[3] = dp[5] = 1

for i in range(6, n + 1):
    if i % 5 == 0:
        dp[i] = dp[i - 5] + 1
    elif i % 3 == 0:
        dp[i] = dp[i - 3] + 1
    elif dp[i - 3] > 0 and dp[i - 5] > 0:
        dp[i] = min(dp[i - 3], dp[i - 5]) + 1

print(dp[n])

💬 Commentary

첫 번째 풀이와는 조금 다른 점이, 배열 초기선언 시에 -1 을 모두 할당해놓기 때문에 4번 조건문이 불필요하다.

👌 Solved Code 3 : 그리디

💡 Idea

그리디로 풀어보고자 했지만, 실패해서 다른 분들의 풀이를 봤다.

나는 n 값에서 5를 빼가면서 체크를 했는데, 3을 빼가면서 5로 나눠지는지 체크했어야 했다.

16 을 예시로 보면, 3씩 빼가면서 5로 나눠지는지 체크한다.

5로 나눠지면 break 문으로 while 문을 탈출한다.

n 값 : 16 → 13 → 10 → 0 → break

이번엔 7을 살펴보자.

n 값 : 7 → 4 → 1

3을 뺀 결과 중에 5로 나눠지는 값이 없다.

즉, 최종 n 이 0이 아니면 배달할 수 없다.

💻 Code

# 그리디 풀이

import sys

n = int(sys.stdin.readline())
result = 0

while n > 0:
    if n % 5 == 0:
        result += n // 5
        n = 0
        break
    else:
        n -= 3
        result += 1

if n:
    print(-1)
else:
    print(result)