[백준] 2839. 설탕배달 Python

문제 링크 : 2839 설탕배달

2839번: 설탕 배달

 

풀이 코드 : GIthub

문제

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

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

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

풀이

백준 문제집에서 DP분류의 문제에서 골랐기에 DP로 접근해야겠다고 생각했다.

 

코드 

import sys

N = int(sys.stdin.readline())
if N == 3 or N == 5:
    print(1)
else:
    dp = [3, 5]
    count = 2
    is_done = False
    flag = True
    while True:
        dump_list = []
        for i in dp:
            sum_3 = i + 3
            sum_5 = i + 5
            print(sum_3, sum_5)
            if sum_3 == N or sum_5 == N:
                is_done = True
                break
            if not sum_3 in dp and not sum_3 in dump_list:
                dump_list.append(sum_3)
                if N > sum_3:
                    flag = False
            if not sum_5 in dp and not sum_5 in dump_list:
                dump_list.append(sum_5)
                if N > sum_5:
                    flag = False
        if is_done:
            break
        dp = dump_list
        count += 1
        flag = True

        if flag:
            count = -1
            break

    print(count)

 

다음과 같은 풀이로 생각하였다.

1. [3, 5]에서 시작하여 각각의 숫자에 +3, +5 를 해 가면서 list를 늘림 여기서 더할 때 중복되는 숫자는 제외

2. 더하다가 찾는 숫자인 N과 만난다면 break 하고 몇 번째 늘릴 때 N을 만났는지 count를 출력

3. 또는 늘린 숫자가 모두 찾는 숫자 N보다 크다면 이제 더이상 N은 찾을 수 없으므로 -1 출력하고 break한다.

 

위 아이디어를 그림으로 나타내면 아래와 같다.

 

결과

 

그러나 시간초과가 발생했다. 

 

제한이 1초인데 N의 최대값인 5000을 찾는데 5초나 걸렸다 ;;

 

 

2번째 풀이

https://puleugo.tistory.com/27

[백준 2839] 설탕 배달 해설 및 풀이 (파이썬)

위 블로그 글을 참고하여 풀었다

 

DP로만 접근하는줄 알았는데 그리디 문제였던 것이다.

 

코드

N = int(input())
if N % 5 == 0:
    print(N//5)
else:
    p = 0
    while N > 0:
        N -= 3
        p += 1
        if N % 5 == 0:
            p += N //5
            print(p)
            break
        elif N == 1 or N == 2:
            print(-1)
            break
        elif N == 0:
            print(p)
            break

 

이번 문제는 다음 4가지 조합으로 결과가 나타날 수 있다.

 

1. N이 5로만 나눠짐
2. N이 5과 3의 조합으로 나눠짐
3. N이 3으로만 나눠짐
4. N이 5와 3으로는 나눠지지 않음

첫번째로 5로만 나누어지는지 체크하고 (N%5==0)

두번째로 모든 5와 3의 조합으로 나누어지는지 체크한다.

마지막으로 나머지가 1, 2 이렇게 남는다면 나누어 지지 않는것이고

3으로만 나눈어진다면 3으로 나눈 결과를 print한다.