기업투자

company_investment.py

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


def maximize(total, cnt, table):
    dp = [[0] * (cnt + 1) for _ in range(total + 1)]
    investments = [[0] * (cnt + 1) for _ in range(total + 1)]

    for company in range(1, cnt + 1):
        for money in range(total + 1):
            if company == 1:
                dp[money][company] = table[money][company]
                investments[money][company] = money
            else:
                for use in range(money + 1):
                    # 신규 기업에 user 만큼 투자 했을 때 단위 이익 + 기존 기업들에 남은 돈으로 투자했을 때 최대 이익
                    profit = table[use][company] + dp[money - use][company - 1]
                    if dp[money][company] < profit:
                        dp[money][company] = profit
                        investments[money][company] = use

    # for row in dp:
    #     print(row)
    #
    # for row in investments:
    #     print(row)

    print(dp[total][cnt])

    each = [0] * (cnt + 1)
    while cnt > 0:
        each[cnt] = investments[total][cnt]
        total -= each[cnt]
        cnt -= 1

    print(' '.join(map(str, each[1:])))


total, cnt = list(map(int, input().split()))
# print('money : %s, cnt : %s' % (total, cnt))
table = [list(map(int, input().split())) for _ in range(total)]
table.insert(0, [0] * (cnt + 1))  # 투자 금액 0에 대한 기업별 이익금(=0) 추가
# print('table : %s' % table)
maximize(total, cnt, table)