파이썬 알고리즘 101 | [백준 2839번] 설탕 배달-나중에 동적계획법으로 풀어보기

Yunny.Log ·2022년 1월 24일

Algorithm

목록 보기

103/318

100. 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 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
예제 입력 3
6
예제 출력 3
2
예제 입력 4
9
예제 출력 4
3
예제 입력 5
11
예제 출력 5
3

<내 풀이>


n=int(input())

if n%5 == 0 or (n%5)%3 == 0 : #최대한 5로 먼저 다 받아주는게 the best
    print(int((n//5)) + int((n%5)//3)) 

elif n%3 == 0 :
    chk = 0
    num  = 1
    maxFive = n//5
    while maxFive > 0 :
        if (n-(5*maxFive))% 3 == 0 :
            chk=1
            break
        else : 
            maxFive-=1
    if chk ==1 : 
        print(int(maxFive) + int((n-(5*maxFive))//3))
    else : 
        print(int(n//3))

else : 
    chk = 0
    num  = 1
    maxFive = n//5
    while maxFive > 0 :
        if (n-(5*maxFive))% 3 == 0 :
            chk=1
            break
        else : 
            maxFive-=1
    if chk ==1 : 
        print(int(maxFive) + int((n-(5*maxFive))//3))
    else : 
        print(-1)

<다른 분의 풀이 or 내 틀린 풀이, 문제점 파악>

- 나의 본래 틀린 코드 (1)


n=int(input())
if (n%5)%3==0 : #최대한 5로 먼저 다 받아주는게 the best
    print(int((n//5)) + int((n%5)//3)) 
elif (n%8)%5==0 : #5*n + 3*m 의 형태일 때 5로 나머지 있는 것 먼저
    print(int(2*(n//8)) + int((n%8)//5))
elif (n%8)%3==0 : #5*n + 3*m 의 형태일 때 3의 나머지처리
    print(int(2*(n//8)) + int((n%8)//3))
elif (n%3)%5==0 : #있어야하나,,?
    print(int((n//3)) + int((n%3)//5))
else : 
    print(-1)

=> 고려 안한 경우 (ex 99)

99라면 물론 3*33 으로 33 으로 나눌 수 있지만 베스트는 5*18 + 3*3 => 21
==> 이걸 어떻게 납득시킬 수 있을까?

사고과정

1) 우선 5로 나눌 수 있으면 무조건 5 봉투로만 구성하도록 처리

2) 그 다음 3으로 나눌 수 있으면
- 2-1) 그 아이를 5의 배수 + 3의 배수로 나눌 수 있는지 검사가 필요

3) 8로 나눠보기(3, 5의 배수에 속하지 않고 3/5가 더해져서 나타난 아이)

4) 그외의 것은 -1 출력

나의 두번째 수정 후에도 틀린 코드

n=int(input())

if n%5 == 0 or (n%5)%3 == 0 : #최대한 5로 먼저 다 받아주는게 the best
    print(int((n//5)) + int((n%5)//3)) 

elif n%3 == 0 :
    chk = 0
    num  = 1
    maxFive = n//5
    while maxFive > 0 :
        if (n-(5*maxFive))% 3 == 0 :
            #(int(maxFive) + int((n-(5*maxFive))//3))
            chk=1
            break
        else : 
            maxFive-=1
    if chk ==1 : 
        print(int(maxFive) + int((n-(5*maxFive))//3))
    else : 
        print(int(n//3))

elif (n%8)%5==0 : 
    print(int(2*(n//8)) + int((n%8)//5))

elif (n%8)%3==0 :
    print(int(2*(n//8)) + int((n%8)//3))

else :
    print(-1)

위가 정답코드고, 밑에가 내 코드인데 값이 무려 6이나 다르게 나온다.
=> 분석 : 142 => 5로 나눠떨어지지 x, 3으로 나눠떨어지지 x
=> 142/8 : 몫 17, 나머지 6
=> 이 케이스는 elif (n%8)%3==0 : print(int(2*(n//8)) + int((n%8)//3)) 에 해당
==> 근데 8로 나눈다는 가정은 애초에 5하나,3하나 이렇게 짝지어 구성돼있음을 가정
===> 근데 3하나가 5개만 모여도 5의 배수가 되는 경우 => 이 경우엔 3*5개 보다 5*3개 로 3개로 치환해주는게 필요..!
====> 따라서 8로 나눠주는 케이스에서도 maxFive 값 두어야 한다, 5를 최대한으로 끼워넣을 수 있는 경우의 수를 찾아내는 것
======> 그럼 8로 애매하게 경우를 나누는 게 아니라 3,5배수 아닌 것들은 싹 다 5로 나누면서 갈 때까지 가보는 방법으로 채택하면 됨

다른 분의 해결방법

1) 동적계획법으로 접근하신 분

출처 : https://myjamong.tistory.com/291

N = int(read())

arr = [5001] * (N+5)
arr[3] = arr[5] = 1

for i in range(6, N+1):
    arr[i] = min(arr[i-3], arr[i-5]) + 1

print(arr[N] if arr[N] < 5001 else -1)

2) 간단한 해결책으로 접근하신 분

출처 : https://ooyoung.tistory.com/81

sugar = int(input())

bag = 0
while sugar >= 0 :
    if sugar % 5 == 0 :  # 5의 배수이면
        bag += (sugar // 5)  # 5로 나눈 몫을 구해야 정수가 됨
        print(bag)
        break
    sugar -= 3  
    bag += 1  # 5의 배수가 될 때까지 설탕-3, 봉지+1
else :
    print(-1)