[백준] 2839. 설탕배달 (파이썬)

 

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

n = int(input())
data = [3, 5]

d = [5001] * (n+1)
for i in data:
    if n < i:
        continue
    d[i] = 1

for j in data:
    for i in range(6, n+1):
        if i <= j:
            continue
        d[i] = min(d[i], d[i-j]+1)

result = d[n]
if result > 5000:
    print(-1)
else:
    print(result)

 

다이나믹 프로그래밍과 그리디 알고리즘을 이용했다고 하는데, 나는 다이나믹 프로그래밍은 이해가 되지만 그리디는 어디에 적용되었는지 잘 모르겠다.

내가 코드를 DP만 적용시킨건가? 근데 백준 그리디 유형에서 가져온 문제다.. 뭘까?

 

어쨌든 해당 문제에서는 배달 가능한 설탕이 3kg 와 5kg 두개뿐이므로 data 리스트에 넣어준다.

1. 문제에서 N은 3 이상 5000이하 라고 했기 때문에 다이나믹 리스트를 모두 5001 로 초기화해주었다.

2. d 리스트의 의미는 해당 인덱스만큼의 설탕을 배달할 떄 필요한 설탕봉지의 개수이다. 그렇기 때문에 d[3]과 d[5]에는 1을 초기화해주어야 한다. (n이 4일 경우를 생각해, n<i일 경우의 조건문을 넣어주었다.)

3. 반복문은 6부터 시작해주었다. 

    설탕 봉지는 3과 5짜리가 있기 때문에, 타겟 번호를 만들기 위해서 타겟-3 번째에서 계산했던 최소 설탕봉지 개수 + 1을 가져오면 된다. 만약 [타겟-3]이 무한을 의미하는 5001이라면 결과 최소 설탕봉지는 계산할 수 없고, 결과값도 5001로만 남게 된다.

5. 해당 인덱스로 접근했을 때, 5001이 나온다면 딱 떨어지는 최소 설탕봉지를 계산할 수 없다는 의미이므로 -1을 출력하고, 아니라면 결과값을 출력한다.