[백준] 2662 - 기업 투자

www.acmicpc.net/problem/2662

2662번: 기업투자

문제를 보자마자 DP로 풀면 되겠다는 생각을 떠올리는 것은 어렵지 않았다.

DP 점화식을 떠올리는 과정이 익숙하지가 않아서 (특히 2차원 이상으로 갈 경우..)

점화식을 고민하고 구현하는데 시간을 많이 쏟았다.

 

문제를 풀고나니 알고리즘 분류에 냅색문제로 되어있는 것을 보았는데,

생각해보니 냅색문제와 점화식을 도출한 과정이 비슷했다.

 

문제를 풀기위해 사고한 과정을 정리하고자 한다.

맨 처음엔 모든 경우의 수를 다 체크해보자고 생각했다.

(이제 와서 든 생각이지만 DP를 떠올려놓고 브루트포스를 고민하고 있었다ㅋㅋ)

 

모든 조합의 경우의 수는 최대 20H300 이다.

20개의 기업들 중 중복을 허락해서 300개를 뽑아야 하기 때문이다.

어림잡아 계산해도 대충 10^38 보다 훨씬 큰 수가 계산 중에 튀어나온다.

대충 300을 19번 곱하고 19! 으로나누면 되는데, 아무리 봐도 숫자가 너무 크다. 

따라서 이 방법은 탈락이었다.

 

그래서 원래대로(?) DP 풀이를 고민하기 시작했다.

일단, 구해야 하는 것은 최대 이익이므로 dp에 저장하는 값은 이익임이 자명하다고 생각했다.

주어진 예제입력을 가지고 고민하다가 한가지 아이디어를 떠올렸다.

 

A, B, C ... X, Y, Z 순으로 차례대로 투자한다고 생각해보자.

B기업까지의 누적투자금액으로 얻는 최대 이익은

직전 A기업까지의 누적투자금액 으로 얻는 이익 + B기업에의 투자금액으로 얻는 이익 아닐까?

 

단순히 이렇게만 보면 점화식이 바로 안떠오른다.

구체화를 시켜보자.

 

B기업까지 투자를 마쳤을 때의 누적투자금액이 i 일때,

지금까지의 투자금액으로 받는 이익의 합을 B[i] 라고 하자.

이때 B기업에 k의 추가적인 투자를 한 결과로 누적 투자금액이 i가 되었다면

k의 추가적인 투자로 얻는 이익이 profit[k] 일 때

B[i] = A[i-k] + profit[k]

와 같이 점화식을 쓸 수 있다.

 

이 점화식을 모든 누적투자금액에 대해 반복하면 된다.

그리고 모든 기업에 대해 반복하면된다.

 

점화식을 고민하는 과정에서 dp배열을 3차원으로 쓰는 것까지 생각했지만,

굳이 그럴 필요가 없음을 깨달았다.

dp배열은 1차원으로 쓰되, 3중 반복문을 돌면서 dp배열을 갱신했다.

 

dp 배열은 단순하게 잡았다.

dp[i] = 누적투자금액이 i만원 일 때 얻는 이익의 최댓값

이때 해당 기업에 투자를 안 할 수도 있기 때문에, dp 배열은 0을 포함해서 잡아야한다.

 

이제 이 dp 배열을 첫번째 기업인 기업 A의 값으로 전부 초기화한다.

예제입력을 예로 들면

 

dp[0] = 기업 A까지의 누적투자금이 0원 = 기업 A에의 투자금이 0원 = 얻는 이익 0

dp[1] = 기업 A에의 투자금이 1만원 = 얻는 이익 5

dp[2] = 얻는 이익 6

dp[3] = 7

dp[4] = 10

 

이렇게 초기값을 세팅해 둔 상태로 3중 반복문을 돈다.

 

A기업의 값을 가지고 B기업의 값을 갱신

B기업의 값을 가지고 C기업의 값을 갱신

....

 

이렇게 큰 틀로는 서로 직전 기업의 정보를 가지고 값을 갱신하므로

우선 기업에 대해 반복을 돈다.

 

이제 선택된 기업 안에서 또 반복을 돈다.

예제 입력의 경우 A기업의 값을 가지고 B기업의 값을 갱신하는 것이다.

이때 갱신은 누적 투자금이 높은 값부터 낮은 값 순서로 갱신해야한다.

 

그 이유는 누적투자금이 낮은 값은, 누적투자금이 높은 값을 갱신할 때도 해당 값이 사용되므로,

누적 투자금이 낮은 값이 한번 갱신되면, 누적투자금이 높은 값을 갱신할 때 기존의 낮은 값이 아닌

갱신된 값을가지고 높은 값을 갱신하기 때문에 DP의 점화식의 각 요소가 의미하는 것이 달라지기 때문이다.

(반대로 누적투자금이 높은 값은 갱신되더라도, 누적투자금이 낮은 값을 갱신할 때 영향을 주지 않는다.)

 

예를 들어 설명하면 이해가 빠르다.

B기업의 누적투자금이 3만원인 경우 이익의 최댓값은

 

A기업의 누적투자금이 0만원인 경우의 이익 + B기업에 3만원을 투자해서 얻는 이익

A기업의 누적투자금이 1만원인 경우의 이익 + B기업에 2만원을 투자해서 얻는 이익

A기업의 누적투자금이 2만원인 경우의 이익 + B기업에 1만원을 투자해서 얻는 이익

A기업의 누적투자금이 3만원인 경우의 이익 + B기업에 0만원을 투자해서 얻는 이익

 

이 4가지 값 중 최댓값이다.

만약 누적 투자금이 낮은 값부터 갱신한다고 가정해보자

 

B기업의 누적투자금이 1만원인 경우 이익의 최댓값은

A기업의 누적투자금이 0만원인 경우의 이익 + B기업에 1만원을 투자해서 얻는 이익 

A기업의 누적투자금이 1만원인 경우의 이익 + B기업에 0만원을 투자해서 얻는 이익 

이 2가지 값 중 최댓값이다.

 

만약 파란색의 경우가 최댓값이라면 문제는 없다.

B기업에 0만원을 투자해서 얻는 이익은 0이기 때문에

파란색이 의미하는 것 자체가, A기업의 누적투자금이 1만원 경우의 이익과 같기 때문이다.

 

하지만 초록색의 경우가 최댓값이라면 문제가 발생한다.

저 경우가 최댓값이라면 이제 dp[1]이 의미하는 바가 달라진다.

원래 dp[1]은 A기업의 누적투자금이 1만원인 경우의 이익 이었다.

그러나 초록색으로 갱신되면 이제 B기업까지의 누적투자금이 1만원인 경우의 이익을 의미한다.

 

그럼 나중에 B기업까지의 누적투자금이 3만원인 경우의 이익을 구할 때,

보라색 부분이 의미하는 값을 dp배열에서는 찾을 수 없게 된다.

 

하지만 반대로 큰 값에서부터 갱신할 땐 이 문제가 발생하지 않기 때문에 거꾸로 갱신해야한다.

이렇게 갱신을 다 마치고 최종 값을 구할 때는

마지막 기업까지의 누적투자금액이 최대인 dp값을 읽으면 된다.

---

하지만 이 문제는 이 dp값으로 끝내지 않는다.

어떤 구성으로 이 dp값이 나왔는지를 알아내야한다.

 

하지만 값이 갱신되는 방식과 시점을 알고 있기 때문에 어렵지 않게 구할 수 있다.

값이 갱신되는 방식과 동일하게 경로를 저장한다.

값을 갱신할 때는 기존값 + 새로운 값을 더한 '하나의 값'으로 갱신했다면

구성값을 갱신할 때는 '기존값이 들어있던 배열'에 '새로운 값' 요소를 넣어주면 된다.

 

갱신과정이 3중 반복문에서 일어나기 때문에,

구성값 갱신을 할 때는 2중 반복문 갱신 때보다 한번 더 생각해야 한다.

이 내용은 구체적으로 설명하기보다 코드를 읽고 이해하는 것이 더 나을 것이라고 판단하여

최종 정답코드를 남기는 것으로 문제 정리를 마치고자 한다.

 

import copy
n, m = map(int, input().split())

# i번째 기업에 j 원을 투자했을 때 얻는 금액
invest = [[0] for _ in range(m)]
for _ in range(n):
    l = list(map(int, input().split()))
    for i in range(1, len(l)):
        invest[i-1].append(l[i])

dp = [0 for _ in range(n+1)]
path = [[] for i in range(n+1)]

for i in range(n+1):
    dp[i] = invest[0][i]
    path[i].append(i)

for i in range(1, m): # 2번째 기업부터 모든 기업에 대해 반복
    for j in range(n, -1, -1): # 해당 기업의 바로 전단계까지의 누적 투자 금액에 대해 거꾸로 반복
        add = 0
        for k in range(1, j+1): # 해당 누적 투자 금액에서 이 기업에 투자해서 얻는 이득 갱신
            if dp[j-k] + invest[i][k] > dp[j]:
                dp[j] = dp[j-k] + invest[i][k]
                path[j] = copy.deepcopy(path[j-k])
                add = k
        path[j].append(add)

print(dp[-1])
print(*path[-1])