개구리

우물 안 개구리

0-1 냅색 문제다. 냅색 알고리즘 유형을 분석하고 풀었더니 생각보다 쉽게 풀 수 있었다.

투자했을 때 최대 이익과 함께 각 기업에 투자한 액수를 출력해야 한다. 각 기업에 투자한 액수를 구하기 위해 dp를 모두 갱신한 뒤 다시 거꾸로 거슬러 올라가며 체크한다.

N, M = map(int, input().split())
company = [[0 for _ in range(M+1)]]
for i in range(N):
    company.append(list(map(int, input().split())))

dp=[[ [0,0] for _ in range(N+1)] for _ in range(M+1)]
for i in range(1,M+1) : 
    
    for j in range(1, N+1):
       
        for k in range(0, j+1):
            tmp1 = dp[i][j][0]
            tmp2 = dp[i-1][j-k][0] + company[k][i]
            
            if tmp1>=tmp2:
                #dp[i][j][0]=tmp1
                #ans[i-1]=ans[i-1]
                pass
            else:
                dp[i][j][0] = tmp2
                dp[i][j][1] = k #k원 투자한 경우에 최대임을 저장

tmp = N
ans=[0 for _ in range(M)]
for i in range(M):
    used = dp[M-i][tmp][1]
    ans[M-1-i]=used
    
    tmp = tmp-used

print(dp[M][N][0])
print(*ans)

풀이

최대 이익이 2**31이므로 최대 이익이 dp에 저장되어야 한다고 추측할 수 있었다. 즉 dp[i][j]에 i번째까지 기업까지 j원을 투자하며 얻을 수 있는 최대 이익을 저장했다.

점화식

i번째 기업까지 j원을 투자해서 얻는 이익은

  • i-1번째 기업까지 j원 투자해서 얻는 이익
  • i-1번쨰 기업까지 j-1원 투자해서 얻는 이익 + i번째 기업이 1원 투자해서 얻는 이익
  • i-1번째 기업까지 j-2원 투자해서 얻는 이익 + i번째 기업이 2원 투자해서 얻는 이익
  • …
  • i-1번째 기업까지 0원 투자해서 얻는 이익 + i번쨰 기업이 j(N)원 투자해서 얻는 이익

중에서 최대 값이다.

이를 반복문을 통해 갱신한다. 갱신할 때 i 번째 기업에 투자한 금액도 같이 dp 배열에 저장한다.

투자 금액 추적하기

dp[M][N]은 M번째 기업까지 N원을 사용하여 얻은 이익으로 최대 이익이다

최대 이익을 얻었을 때 M번째 기업에 투자한 금액이 dp[M][N][1]에 저장되어 있다.

이 때 M-1번째 기업에는 N-(M번째 기업에 투자한 금액)만큼 투자했다.

M-2번째 기업에는 N-(M번째 기업에 투자한 금액)-(M-1번째 기업에 투자한 금액)을 투자했다.

M번째 기업부터 1번째 기업까지 반복문을 통해 거꾸로 dp를 추적하며 투자한 금액을 구할 수 있다.

댓글남기기

참고