[BOJ/백준] 3056 007

import sys

def find_agent(agent,task):
    if agent == N:
        return 1
    
    if dp[task] != -1:
        return dp[task]

    for i in range(N):
        if not (task & 1<<i):

            temp = find_agent(agent+1,task|1<<i)*arr[agent][i]/100
            if temp > dp[task]:
                dp[task] = temp
    
    return dp[task]
input = sys.stdin.readline
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]


dp = [-1 for _ in range(2**N+1)]




find_agent(0,0)

print(dp[0]*100)

 

 

문제를 푸는방식은 다음과 같다. 

 

각 task를 비트로 구분을 하게 한다.

 

 

이 문제에서 최대 20개의 임무가 있으므로, 2^20으로 비트를 구분해낼수 있다.

 

이러한 점을 이용해, 각자리의 비트는 그와 대응되는 일을 맡는것으로 가늠할 수 있다.

 

그래서 우리는 재귀를 이용해, 현재까지 선택된 task에서 선택되지 않은 task를 선택해 재귀를 한뒤,

 

그 결과값들을 최대값으로 갱신을 해주면 되는 문제이다.

 

또한 중복되는 일을 방지하고자, task별로 값을 저장한뒤에 그 값이 초기값이 아니면 되돌려주는 작업을 해주었다.