백준 2662번 기업투자

문제 링크 : https://www.acmicpc.net/problem/2662

문제풀이

사용한 알고리즘 : DP

(1) 코드 7~8

 'dp[x][k] : 1이상~x이하 기업에 k원을 투자하여 얻을 수 있는 최대 이익' 이라고 설정했습니다.

 최종 얻는 최대 이익은 dp[M][N] 일 것입니다.

(2) 코드 9~11

 최대 이익을 얻기 위해 각 기업에서 얼만큼 투자를 했는지 추적하는 배열입니다.

 'path[x][k] : dp[x][k]를 최대로 만들 때, x기업에 투자하는 금액' 이라고 설정하였습니다.

 

 input:

 3 3

 1 5 2 3 

 2 6 5 7

 3 7 9 8

 인 예를 들어보면 다음과 같이 생각할 수 있습니다.

투자금액 \ 기업	1	2	3
1	5	2	3
2	6	5	7
3	7	9	8

 

 DP와 이에따른 path 표를 짜보면 다음과 같습니다.

금액 \ 기업	1		2		3
	dp	path	dp	path	dp	path
1	5	1	5	0	5	0
2	6	2	7	1	8	1
3	7	3	10	2	12	2

 예를 들어 ,

 dp[3][3] = 12

            = 기업 1에 1을 투자해 5 얻음 + 기업 3에 2를 투자해 7 얻음

 입니다.

 따라서 path[3][3] = 2

                        = 1~3기업에서 3원으로 최대 이익을 얻을 때 3기업에 투자한 금액은 2

 입니다.

(3) 코드 22~36

 과정(2)의 생각에 따라 모든 기업, 투자 금액에 따른 dp값과 path값을 구합니다.

 

(4) 코드 38

 구하고자 하는 답은 'dp[M][N] : 1~M 기업에서 N 금액으로 얻는 최대 이익' 입니다.

(4) 코드 39~51

 최대 이익을 얻기 위해 각 기업에 투자한 금액을 각각 구해줍니다.

 탐색은 N기업에서 역으로 진행됩니다.

 각 탐색시, dp값을 구하기 위해 현재 기업에 투자한 금액을 구한 뒤,

 이를 총 투자금액에서 빼주면서 탐색을 진행합니다.

 위의 예를 들면,

 dp[3][3] = 12 이고, path[3][3] = 2 입니다.

 즉 3 기업에 투자한 금액은 2 입니다.

 따라서 다음 탐색에서는 dp[2][3-2] 를 생각합니다.

 dp[2][1] = 5 이고, path[2][1] = 0 입니다.

 즉 2 기업에 투자한 금액은 0 입니다.

 마지막 탐색에서는 dp[1][1-0] 을 생각하겠죠?

 dp[1][1] = 5 이고, path[1][1] = 1 입니다.

 즉 1 기업에 투자한 금액은 1 입니다.