백준 2839 설탕 배달 - 파이썬

 

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

2839번: 설탕 배달

 

 

dp와 수학 두 가지 방법으로 풀었다.

 

 

 

 

- dp 풀이

dp 배열을 선언해 여기에 답을 저장해가며 풀 수 있다.

dp[n]은 n kg의 설탕을 옮기는 데 필요한 최소한의 봉지의 수를 의미한다.

 

계산이 귀찮지 않도록 dp[3]과 dp[5]는 1로 초기화해 준다.

dp의 길이가 (N+1)이 아니라 max(6, N+1)인 이유는 초기화 과정에서 index 에러가 발생하지 않도록 하기 위함이다.

 

 

 

6 kg부터 N kg까지 for문을 통해 순회하며 필요한 봉지의 수를 계산한다.

 

# 1   만약 (n-3) kg을 옮길 수 있다면, 그것보다 봉지 하나를 더 쓰면 된다. dp[n]을 (dp[n-3]+1)로 갱신해 준다.

# 2   만약 (n-5) kg을 옮길 수 있다면, dp[n]을 (dp[n-5]+1)로 갱신해준다. 다만 (n-3) kg도 옮길 수 있다면, dp[n](이미 갱신함)과 (dp[n-5]+1) 중 더 작은 수의 봉지를 사용하는 경우로 갱신해 준다.

 

 

dp[N]이 0이라면 N kg의 설탕을 옮길 수 없다는 의미이므로 -1을 출력하고, 아니라면 dp[N]을 출력하면 된다.

 

 

N = int(input())
dp = [0] * max(6, N+1)

dp[3], dp[5] = 1, 1

for n in range(6, N+1):
    # 1
    if dp[n-3]:
        dp[n] = dp[n-3] + 1
	
    # 2
    if dp[n-5]:
        if dp[n-3]:
            dp[n] = min(dp[n], dp[n-5] + 1)
        else:
            dp[n] = dp[n-5] + 1

print(dp[N]) if dp[N] else print(-1)

 

 

dp가 더 깔끔하고 틀릴 확률도 더 낮아 보인다.

 

 

 

 

 

 

 

- 수학 풀이

가능하다면 3kg 봉지보다는 5kg 봉지를 많이 써야 한다는 점에서 출발한 풀이이다.

 

 

#1

설탕의 무게가 5kg로 나눠 떨어질 때까지 3kg씩 덜어내 본다.

덜어내면서 사용하는 봉지도 카운팅해 준다.

 

나눠 떨어지지 않더라도 만약 남은 무게가 5kg 이하라면 최종 계산을 해주기 위해 스톱한다.

 

 

# 2

최종 정산을 해준다.

 

남은 설탕의 무게가 5로 나눠 떨어진다면 설탕을 담고 끝낸다.

그렇지 않다고 해도 3으로 나눠 떨어진다면 3kg 봉지에 잘 담아서 마무리한다

둘 다 해당되지 않는다면 불가능한 경우이므로 -1를 출력하면 된다.

 

N = int(input())
answer = 0

# 1
while N >= 5 and N % 5:
    answer += 1
    N -= 3

# 2
if N % 5 == 0:
    answer += N//5
elif N % 3 == 0:
    answer += N//3
else:
    answer = -1

print(answer)

 

 

 

 

설탕 무게의 나머지, 리얼 숫자만을 고려한 풀이도 가능하긴 하다.

예외 처리를 인간이 해준 거라 구리구리한 풀이이다.

 

N = int(input())
answer = -1

if N % 5 == 0:
    answer = N//5
elif N % 5 == 1:
    answer = (N-6)//5 + 2
elif N % 5 == 2 and N >= 12:
    answer = (N-12)//5 + 4
elif N % 5 == 3:
    answer = (N-3)//5 + 1
elif N % 5 == 4 and N >= 9:
    answer = (N-9)//5 + 3

print(answer)