[파이썬/python] 백준 24460 - 특별상이라도 받고 싶어

 

문제

https://www.acmicpc.net/problem/24460

---

문제 설명

1. $N*N$크기만큼 의자가 존재하며, 각 의자에는 번호가 적혀있다.
2. 전체 크기를 정사각형 4개로 나누어 각 구역에서 한명씩 뽑는다. 해당 과정을 재귀적으로 반복한다.
3. 각 구역에서 뽑힌 네 명 중 추첨 번호가 두 번째로 작은 사람이 뽑힌다.
4. 경품을 받기 위해 앉아야 하는 의자 번호를 출력한다.

---

풀이

단순 분할정복을 통한 재귀 문제이다.

 

1. 구역을 네 등분으로 나누어 재귀한다.
2. 구역의 크기가 1이되면 해당 위치의 추첨 번호를 반환한다.
3. 각 구역의 추첨 번호를 받아 두번째로 작은 추첨번호를 반환한다.

---

코드

import sys
input = sys.stdin.readline

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


def recursion(n, row,col):
    if n == 1:
        return arr[row][col]
    else:
        tmp1 = []
        
        tmp1.append(recursion(n//2, row,col)) 
        tmp1.append(recursion(n//2, row ,col + n//2))
        tmp1.append(recursion(n//2 , row + n//2 ,col ))
        tmp1.append(recursion(n//2 , row + n//2,col + n//2))
        return sorted(tmp1)[1]

print(recursion(N, 0,0))

---

시간복잡도

• 가로와 세로의 크기는 $N$이고 분할정복을 통한 재귀의 깊이는 $log_2N$이다.
• 따라서 시간 복잡도는 약 $O(N^2logN)$이다.