[코드트리][Python] 수들 중 최솟값 최대화하기

https://www.codetree.ai/trails/complete/curated-cards/test-maximin-of-numbers/description

Code Tree | Learning to Code with Confidence

 

코드 (백 트래킹)

n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]
col_visited = [False for _ in range(n)]
answer = []
max_ans = -1

def permutation_get_min_arg(cur_row):
    global max_ans
    if cur_row == n:
        max_ans = max(max_ans, min(answer))
        return

    for cur_col in range(n):
        if col_visited[cur_col]:
            continue

        col_visited[cur_col] = True
        answer.append(grid[cur_row][cur_col])

        permutation_get_min_arg(cur_row + 1)

        answer.pop()
        col_visited[cur_col] = False

permutation_get_min_arg(0)
print(max_ans)

 

풀이

이전에 풀었던 문제와 유사하게 순열을 만들고, 이 안에서 최대 값인 원소를 찾아서 저장해줍니다.

이후 다른 재귀함수에서 순열을 완성하게 되면 순열을 이루는 요소 중 최소 값을 찾아서 이전까지 최대 값인 원소와 비교해줍니다.