백준 4781 : 사탕가게 (Python)

본문 링크

import sys
input=sys.stdin.readline

while True:

    N,M=map(float,input().split())
    if N==0 and M==0.00:
        break
    N=int(N)

    dp= [0]*( int(M*100+0.5)+1)
    L=[ [0,0] ]
    for i in range(N):
        a,b=map(float,input().split())
        L.append([int(a) , int(b*100+0.5)])

    for i in range(1,N+1):
        for j in range(1,int(M*100)+1):
            weight=L[i][1] ; value=L[i][0]
            if j>=weight:
                dp[j] = max(dp[j - weight] + value, dp[j - 1], dp[j])
                weight += L[i][1]; value += L[i][0]
            else:
                dp[j]=max(dp[j],dp[j-1])
    print(dp[-1])

📌 어떻게 문제에 접근할 것인가?

단순히 배낭문제를 조금 활용한 문제이다.
물건의 칼로리와 가격이 주어졌을때 중복사용을 허용하여 만들수 있는
최대 칼로리 값이다.

다만 까다로운 점은 사탕의 중복사용이 가능하다는 점이고 문제에서 주어지는 수의 범위이다.

$n,m-(1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00)$

$n$ 이 5000 이하고 $m$ 은 자연수로 바꾸면 사실상 1부터 10000까지이기 때문에
2차원 dp 배열 풀이는 불가능하게 된다.

따라서 우리는 1차원 dp 배열을 사용함으로써 최대 5000x10000 (5천만) 까지 연산만 수행해야한다.

2차원 dp를 사용하거나 3중 반복문을 사용하게 되면 시간초과&메모리초과가 발생한다.

📌 1차원 dp 접근 방법

$dp= [0] × (int(M×100+0.5)+1)$ 로 잡아주자.
이후 입력받은 사탕의 범위만큼 반복문을 하나 돌려주고 dp 배열 크기만큼 반복문 하나를 돌려줘서 총 2개의 반복문을 사용할 것이다.
다만 우리는 사탕을 중복해서 사용가능하기 때문에
$weight=L[i][1], value=L[i][0]$ 라고 잡고 사탕을 구매할수 있을때
$dp[j] = max(dp[j - weight] + value, dp[j - 1], dp[j])$ 로 잡는다.

그리고 가장 중요한 부분인 $weight += L[i][1]; value += L[i][0]$ 를 추가해야한다. 이는 사탕을 한번 추가하고 또 사탕을 추가하는 연산을 반복문으로 탐색하지 않고 덧셈연산으로 처리 가능하다.

만약 사탕을 추가하지 못할 경우에는 $dp[j]=max(dp[j],dp[j-1])$ 로 최대값을 유지해준다.

마지막으로 dp[-1]을 출력하면 결과값이 나온다.

✅ 코드에서 주의해야할 부분

• 0.29 같은 몇몇 수들은 100을 곱하면 28.999999...으로 되기 때문에 $int(M×100+1)$ 로 설정햊준다.
• N==0 and M==0.00 일때 break 문을 넣어준다.
• $N$ 은 반복문에서 1부터 시작하기 때문에 처음에 빈리스트에 [0,0] 값을 넣어준다.