문제

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

문제유형

DP, 냅색문제

접근방법

냅색알고리즘을 모르면 해결할 수 없다. 냅색알고리즘을 사용해서 DP 점화식 세워서 문제해결

점화식 세우는 과정

1. 점화식을 세우기 위해 DP 배열 정의

• DP[금액][기업] : 배열에 정해진 금액만큼 투자하고, 특정기업까지 투자했을 때 최대값

2. 투자금액이 주어진 상태에서 각 기업의 이익의 최댓값을 구하기 위해서는 for문을 사용해서 구해야한다.

• ex)투자금액 4이고 두개의 기업이 존재할때, 이익의 최댓값을 구하기 위해서는 아래와 같이 투자할 수 있는 경우 중 최댓값 찾아서 DP배열에 저장해야한다.
  A:0,B:4
  A:1,B:3
  A:2,B:2
  A:3,B:1

점화식

for i in range(투자금액):
	for j in range(기업개수):
		for k in range(i):
 			DP[i][j] = max(dp[i][j-1], dp[k][j-1]+[i-k][j]

고민했던 내용

DP에만 신경써서 해결하다보니 처음에 각 기업별로 얼마씩 투자했는지에 대한 로직을 전혀 고려하지 않았다. 이 부분도 생각보다 고려하는게 까다로웠다.

코드

1~10Line: 투자금액, 기업갯수 및 기업 이익테이블 입력으로 받아서 처리
10~25Line: 위에서 설계한 DP점화식을 통해 Max값 구한 후 dp[i][j-1] maxValue 크기비교해서 DP테이블 업데이트

numInvest, numCompany = list(map(int, input().split()))

listTable = [[0 for _ in range(numCompany + 1)]]

dp = [[0] * (numCompany+1) for _ in range(numInvest+1)]
dpPos = [[[0 for _ in range(numCompany+1)] for _ in range(numCompany+1)] for _ in range(numInvest+1)]

for i in range(1, numInvest+1):
    listTable.append(list(map(int, input().split())))

for i in range(1, numInvest+1):
    for j in range(1,numCompany+1):
        maxValue = 0
        for k in range(i):
            if dp[k][j-1]+listTable[i-k][j] > maxValue:
                maxValue = dp[k][j-1]+listTable[i-k][j]
                maxPos = dpPos[k][j-1][:]
                maxPos[j] = i-k
        if maxValue > dp[i][j-1] :
            dp[i][j] = maxValue
            dpPos[i][j] = maxPos[:]
        else:
            dp[i][j] = dp[i][j-1]
            dpPos[i][j] = dpPos[i][j-1][:]
            
print(dp[numInvest][numCompany])
print(*dpPos[numInvest][numCompany][1:])