백준 2839번: 설탕 배달 (실버 4, 파이썬 코드)

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

def sugar(n):
    if n > 0:
        if n%5 == 0: return n//5
        else:
            if n>=3 and (n-3)%5 == 0: return n//5+1
            elif n>=6 and (n-6)%5 == 0: return n//5+1
            elif n>=9 and(n-9)%5 == 0: return n//5+2
            elif n>=12 and (n-12)%5 == 0: return n//5+2
    return -1


n = int(input())
print(sugar(n))

메모리 31256 KB, 시간 40ms

완전탐색이라고 생각하지 않고 그냥 수학적으로 먼저 풀어봤다.
조건은 간단하다.
k = 5n+3m (이 때 n과 m은 0 이상의 정수) 꼴로 표현할 수 있으면 적어도 -1을 리턴하진 않는다.

그렇다면 생각해보자.
5n+3m에서 최대한의 n값과 최소한의 m값을 사용해야한다.

3의 배수를 찬찬히 뜯어보면 다음과 같다.
3, 6, 9, 12, 15, 18, 21, 24, 27, 30 ...

3 1 = 3
3 2 = 6
3 3 = 9
3 4 = 12
3 5 = 15 <- 전환점
3 6 = 18 = 3 1 + 3 5
3 7 = 21 = 3 2 + 3 * 5

따라서 염두에 둘 3의 배수는 3, 6, 9, 12 뿐이다.
이걸 대충 풀면 저 코드가 된다.

빠른 점은 좋다.

알고리즘: 그리디 알고리즘
난이도: 실버 4