[백준-파이썬] 17829: 222-풀링

문제 풀러 가기

행렬의 한 쪽 길이 N이 주어진다. 이 행렬에서 2X2 정사각형씩 보면서, 그 중에 2번째로 큰 수를 모아서 새로 행렬을 만든다. 그러다가 1X1 행렬이 되면 그때 남은 값을 출력해야 한다!

그러면 처음에는 행렬의 한 변은 처음에는 N이었다가 그 후에는 N//2가 된다. 그러다가 1이 되면 그때의 값을 리턴해야 하니까 그걸 종료 조건으로 생각했다. 

또 2X2 정사각형들이 있을텐데, 그런 정사각형은 N//2 X N//2가 있다. 또 N//2 X N//2 사이즈의 새로운 리스트(tmp_arr)가 생기니 그 사이즈로 리스트를 만들어뒀다.

정사각형들의 가로 인덱스들은 0X2, 1X2, .... (N//2)X2에서 출발하게 된다. 세로 인덱스들도 마찬가지이다. 그 인덱스에서 시작해서 그 다음 인덱스까지 봐주게 된다. 그렇게 4개씩 봐주면서, 그 값들을 tmp 리스트에 저장했다. 4개씩 다 본 후에 tmp를 sort해서 두번째로 큰 수를 뽑아준다. tmp_arr의 해당 위치에 그 값을 넣어준다. 

tmp_arr를 다 채우면 arr을 tmp_arr로 바꿔준 후에, 다시 재귀 함수를 실행한다. 이때는 한 변의 길이가 N//2가 되었으니 n//2를 넣어준다.

 

처음에는 return sol(n//2)를 안하고 그냥 sol(n//2)를 해서 틀렸다. ㅠ return 을 해야 n==1에서 리턴한 값이 제대로 출력된다.

import sys

input = sys.stdin.readline

N = int(input())
arr = list(list(map(int, input().split())) for _ in range(N))


def sol(n):
    global arr
    if n == 1:
        return arr[0][0]

    tmp_arr = [[0] * (n // 2) for _ in range(n // 2)]

    for i in range(n // 2):
        for j in range(n // 2):
            # 2X2 칸 중에 두 번째로 큰 수 구하기
            tmp = []
            for ii in range(i * 2, i * 2 + 2):
                for jj in range(j * 2, j * 2 + 2):
                    tmp.append(arr[ii][jj])
            tmp.sort()
            tmp_arr[i][j] = tmp[2]
    arr = tmp_arr
    return sol(n // 2)


print(sol(N))