[ SW Expert Academy ] 5209. 최소 생산 비용

알고리즘을 이해 하고 문제에 적용시키는 .. 그런 느낌이 든다.

2-3일 새에 또 코테 이해력이 늘어난 느낌이다.

백트래킹이 참 이해 안 가는 파트 중에 하나였는데.. 그동안 그냥 머리에 밀어넣기 암기 식으로 문제 풀어온 성과인지, 해당 사이트의 30분도 안 되는 강의 덕분인 지, 조금은 논리적으로 한 큐에 해당 문제를 풀 수 있었다.

이게 좀 간단한 문제여서 뿌듯함까지는 아니고 신기함이 강렬하게 느껴진다. 

이런 사소하고 소중한 작은 성취 덕분에 일주일 간 코테에 집중할 스케줄이 더욱 기대가 된다.

 

 

 

1차 제출 [ 10 / 10 ] Pass

 

 

def dfs(plants, n, selected, depth, curr_sum):
    global answer
    if depth == n:
        answer = min(answer, curr_sum)
        return
    if curr_sum > answer:
        return
    for i in range(n):
        if i not in selected:
            selected.append(i)
            dfs(plants, n, selected, depth+1, curr_sum+plants[depth][i])
            selected.pop()
    return answer

if __name__ == "__main__":
    T = int(input())
    for test_case in range(1, T+1):
        n = int(input())
        plants = [list(map(int, input().split())) for _ in range(n)]
        answer = 1e9

        dfs(plants, n, [], 0, 0)
        print("#{} {}".format(test_case, answer))