문제 링크
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc
계획
전에 풀어봤던 문제이기 때문에 전보다 깔끔하게 코드를 짜고 실행시간을 줄이는 게 목표였다. DFS를 이용하되, 가지치기가 꼭 필요한 문제. 그리고 정수로 입력이 들어오지만 확률을 계산해야 하기 때문에 어디서 /100, *100을 해줄 지도 고민이었다.
코드
def select_work(row, now, remaining):
global max_v
if row == N:
max_v = max(max_v, now)
return
for i in range(len(remaining)):
tmp = now * (arr[row][remaining[i]] / 100)
if tmp <= max_v:
continue
select_work(row + 1, tmp, remaining[:i] + remaining[i + 1:])
T = int(input())
for tc in range(1, T+1):
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [0] * N
max_v = 0
select_work(0, 1, [n for n in range(N)])
print('#{} {:.6f}'.format(tc, max_v * 100))풀이 방법
시간 복잡도를 줄이기 위해서 재귀함수 호출을 하기 전에 가지치기를 하도록 했다. 그리고 원래는 row == N일 때 now에 100을 곱하며 max_v 자체에 계산된 확률 값이 담기도록 했는데 그러면 for문 내에서 tmp에도 100을 곱해주어야 하기 때문에 마지막에 결과를 출력할 때만 100을 곱해주도록 변경했다. 이렇게 수정했더니 시간이 5초에서 4초대로 줄어 들었다! DFS는 이제 크게 어렵지 않게 풀 수 있는데 시간 복잡도를 줄이는 건 앞으로도 많이 고민해봐야 할 듯하다.
