[BOJ 23061, Python 3] 백남이의 여행 준비

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

23061번: 백남이의 여행 준비

알고리즘 학회 beans3142님의 풀이를 들음

C++은 오버플로가 문제던데 어디서 오버플로가 나는지 모르겠어서 정신 나갈 뻔하다가 파이썬으로 제출해서 통과함 출력문이 있는지 모르고 무지성으로 제출하다가 계속 틀렸음 ㅋㅋ

 

 

풀이

문제를 보자마자 냅색문제인 것을 알 수 있습니다.

일반적인 냅색문제랑 살짝 다른 점은 가방에 1개가 아닌 M개라서 이중에서 효율이 좋은 가방을 선택하라고 합니다.

 

그러면 가방 M개를 일일이 냅색을 돌리지 말고 M개의 가방중에서 가장 용량이 큰 가방을 기준삼아 냅색을 돌리면 됩니다.

이렇게 냅색을 돌렸으면 이제 dp[n][i번째 가방무게]의 값은 물품 N개를 선택적으로 골라 i번째 가방무게에 넣을 수 있는 최대 가치가 됩니다.

이제 효율성을 구해야하는데 단순 나눗셈을 하면 소수점이 나오므로 무조건 안되고, 다른 방식이 필요합니다.

 

저는 몫과 나머지를 생각했는데

2 2

30 40

50 60

30

50

 

으로 하면 전부 몫이 1이고 나머지가 10인 값이 나옵니다. 이때 40/30 = 1.3333....이고, 60/50은 1.2가 나옵니다.

 

그래서 몫과 나머지가 아닌 효율성을 분수꼴로 표현할 수 있으므로 최대공약수와 최소공배수를 이용하여 문제를 풀면 됩니다.

 

 

코드

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)
def lcm(a, b):
    return a * b // gcd(a, b)
 
n, m = map(int, input().split())
thing = [[0,0]] + [[*map(int, input().split())] for _ in range(n)]
bag = [0] + [int(input()) for _ in range(m)]
 
dp = [[0] * (max(bag)+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(max(bag) + 1):
        dp[i][j] = max(dp[i][j], dp[i-1][j])
        if j - thing[i][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i-1][j-thing[i][0]] + thing[i][1])
 
ans = 1
for i in range(2, m+1):
    LCM = lcm(bag[ans], bag[i])
    val1 = dp[n][bag[ans]] * LCM // bag[ans]
    val2 = dp[n][bag[i]] * LCM // bag[i]
    if val2 > val1: ans = i
print(ans)