[백준] 2839. 설탕 배달 - Python

[Silver IV]

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

2839번: 설탕 배달

풀이

<풀이 1>

Dinamic programming을 통해 해결

3 - 3 * 1 => 1

4 => -1

5 - 5 * 1 => 1

6 - 3 * 2 => 2

7 => -1

8 - 5 * 1 + 3 * 1 => 2

9 - 3 * 3 => 3

10 - 5 * 2 => 2

11 - 5 * 1 + 3 * 2 => 3

12 - 3 * 4 => 4

13 - 5 * 2 + 3 * 1 => 3

14 - 5 * 1 + 3 * 3 => 4

...

결과를 나열해보면서 규칙성을 찾았다.

규칙은 "dp[i] = min(dp[i - 3], dp[i - 5] + 1)". 즉, 3 or 5번째 이전의 수 중 작은 수에 1 더한 값이 자기 자신이 된다.

0, 1, 2, 4일 때는 이전에 예외처리를 해주고 규칙성을 찾으면 된다.

n = int(input())

dp = []

dp = [5001, 5001, 5001, 1, 5001, 1]



for i in range(6, n + 1):

    dp.append(min(dp[i - 3], dp[i - 5]) + 1)



if dp[n] < 5000:

    print(dp[n])

else:

    print(-1)

<풀이 2>

주어진 규칙을 활용하여, 수식을 반복적으로 계산해 문제를 해결했다.

1. 5의 배수가 아니면서, 3보다 클 경우 3을 빼고, cnt를 1만큼 증가시킨다.

(이후 다시 반복. n을 5의 배수로 맞춰주는 과정. why? -> 최대한 적은 봉지를 사용해야 함)

2. 5의 배수일 경우 n을 5로 나눈 몫을 cnt에 더한다.

(몫으로 나누는 이유는 n을 /로 나눌 경우 실수형으로 계산되기 때문에 출력에 문제가 생김)

3. 위 과정을 반복하여 1, 2 모두 해당되지 않으면 계산할 수 없기 때문에 cnt = -1

n = int(input())

cnt = 0



while True:

    if n % 5 != 0 and n >= 3:

        n -= 3

        cnt += 1

    elif n % 5 == 0:

        cnt += n // 5

        n /= 5

        break

    else:

        cnt = -1

        break

print(cnt)