[python]백준 2839번 : 설탕 배달

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

나의 답

# 백준 2839번 : 설탕 배달
# 2020-02-01

num = int(input())
count = 0

while num>=3 :
    if not(num%5) : # 5의 배수이면
        count+= num/5
        break
    else :
        count+=1
    num-=3

if num==1 or num==2:
    count = -1
else :
    count += 0

print(int(count))

분석

1. 다이나믹 알고리즘

    앞선 2문제의 영향으로 처음에는 모든 경우의 수를 찾아볼까 생각했다. 하지만 이전 문제와 달리 수의 범위가 확연히 커진데다가 연산의 시간이 너무 오래걸릴 것 같아서 이러한 방식은 아닐 거라고 결론 내렸다.

2. 경우의 수 (특징 찾기)

    그렇다면 뭔가 특징이 있고, 어떤 수는 어떻게 처리할 지에 대한 규칙이 있지 않을까 싶어 예제에 나온 수를 비롯해 여러 가지 수들을 쓰면서 논리의 흐름을 보았다.

    우선 어떠한 수가 주어지면 5로 나누어보고 나뉘어지면 5kg의 봉지만 사용하는 것이 가장 최소의 봉지를 사용할 수 있는 방법임은 확실했다.

    그렇다면 5로 나뉘어지지 않는 수는 어떻게 되는 것일까? 그 예로 21을 계산해보니 3kg * 7개도 가능하지만 5kg*3개, 3kg*2개 가 더 적은 봉지 수로 21kg를 옮길 수 있었다.

    이런 두 가지 상황으로 유추해볼 때

   5kg 봉지만 사용 > 5kg + 3kg 섞어서 사용 > 3kg 봉지만 사용 > 표현 불가

   이러한 우선순위로 적용되는 것을 알 수 있었다. 그리고 이러한 방법이 적용되는 수는

   5의 배수 > 3의 배수를 빼면 5의 배수가 되는 수 > 3의 배수만을 만족하는 수 > 표현 안되는 수 이다.

   특히 2번째의 3의 배수를 빼면 5의 배수가 되는 수는 5의 배수를 빼면 3의 배수가 되는 수로도 나타낼 수 있겠지만 연산시 5의 배수를 구하는 것이 더 빠르다고 생각해서 전자로 잡았다.

 그림으로 나타내면 다음과 같다.

 주어진 N이 바로 5로 나누어진다면 N은 5의 배수고 위에서 설명한 첫번째 경우에 해당한다. 따라서 5kg 봉지만으로 이동할 수 있다.

 바로 5로 나누어지지 않는다고 해도 N에서 3을 빼면서 count를 더해가면 count는 3kg 봉지의 갯수만큼 더해지게 된다. 그리고 N에서 3의 배수를 뺀 어떤 수가 5로 나누어지는 수가 된다면 이 때껏 더해진 count 수(3kg 봉지의 수)에다가 현재 수를 5로 나눈 몫(5kg 봉지의 수)를 더하면 된다. 이는 두번째 경우에 해당하며 5kg, 3kg 봉지를 섞어서 이동할 수 있다.

 N에서 3을 빼는 과정을 계속 반복했더니 남은 수가 3보다 작아졌다면 2가지 케이스가 남았다. 마지막 남은 수가 0이라면 N은 3으로만 이루어진 3의 배수이다. 따라서 이때껏 더해온 count 수가 곧 3kg 봉지의 수이며 세번째 경우에 해당한다.

 하지만 남은 수가 1 또는 2라면 이는 앞선 3가지 경우 모두 해당하지 않고 심지어 3의 배수도 아니다. 따라서 어떤 방식으로도 설탕은 정확히 옮길 수 없다. 이는 4번째 경우에 해당하며 count 값으로 -1을 할당하여야한다.

예제

 어떤 수 N이 21이라고 두고 예제로 설명하겠다.

21은 5로 나누어지지 않으므로 3을 빼고 count에 1을 더한다. (현재 count는 1). 18은 5로 나누어지지 않으므로 다시 3을 빼고 count에 1을 더한다. (현재 count는 2). 15는 5로 나누어지므로 5로 나눈 몫을 count에 더한다. 3+2 (몫+현재count) = 5.

 즉, 설탕 21kg은 5kg 봉지 3개와 3kg 봉지 2개로 정확히 배달할 수 있다.

다른 답

2020-04-19 추가

간단한 알고리즘으로 바꿀 수 있다.

def func(N): // N을 받아서
    for i가 0부터 N/5까지 돌면서 // 5가 나올 수 있는 횟수
        N에서 5*i를 빼고 count에 i 더하기 (5 나온 횟수)
        남는 수(n)가 3의 배수면
        n/3을 count에 더하기 (3 나온 횟수)
        min 계산

 간단히 설명하자면, 5kg 짜리가 나올 수 있는 경우의 수를 모두 세면서 3으로 나누어떨어지는 지 확인하고 나누어떨어지는 경우에 한해서 count를 비교하는 방식이다.

 예를 들어 설명하자면 21이라는 수가 있을 때, 5는 최대 4번까지 나올 수 있으므로 for문을 0~4까지 돈다. 5가 한번도 안나오는 경우인 i가 0인 경우를 보면 남는 수는 21이고 3의 배수이기 때문에 21/3 = 7을 count에 더하면 총 count는 7이다. 즉, 21은 5키로 0개와 3키로 7개로 배달할 수 있다.

 이렇게 i를 돌다가 i가 3인 경우를 보자. i가 3인 경우에 21-5*3 = 6 이므로 count에 3을 더하고 남는 수 6이 나타난다. 6이 3의 배수이므로 6/3 = 2를 count에 더한다. count는 5이므로 이전에 나왔던 7보다 작다. 따라서 min 계산에서 5가 최소로 나온다.