Hikenny25
24460 - 특별상이라도 받고 싶어 본문
https://www.acmicpc.net/problem/24460
24460번: 특별상이라도 받고 싶어
첫 번째 줄에는 정수 $N$이 주어진다. (단, $N = 2^m$, $0 \le m \le 10$, $m$은 정수) 두 번째 줄부터 $N$개 줄의 $i$번째 줄에는 $i$번째 줄에 있는 의자에 적힌 추첨번호가 주어진다. 각 줄에는 $N$개의 추첨
www.acmicpc.net
- 분할정복법
def flatten(arr):
return arr[0][:] + arr[1][:]
def get_second_min(arr):
arr = sorted(arr)
return arr[1]
def divide(arr):
if len(arr) == 2:
return [get_second_min(flatten(arr))]
l = len(arr) // 2
divided_array = list()
for i in [0, l]:
for j in [0, l]:
divided_array.append([row[j:j+l] for row in arr[i:i+l]])
for i in range(4):
divided_array[i] = divide(divided_array[i])
last_array = [divided_array[i][0] for i in range(4)]
return [get_second_min(last_array)]
n = int(input())
number = [list(map(int, input().split())) for _ in range(n)]
if n == 1:
print(number[0][0])
exit()
print(divide(number)[0])
SWEA 5일차 - 토너먼트 카드게임과 같은 분할정복법으로 푸는 문제이다!!!
응용해서 풀어보앗다 어느정도 이해가 되는듯ㅎ
Comments