17829

날짜 : 2023. 04. 06

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10**6)

n = int(sys.stdin.readline())
graph = list()
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))  # 그래프 입력
dx = [0, 0, 1, 1]
dy = [0, 1, 0, 1]


def dac(r, c, l):
    if l == 0: return graph[r][c]
    temp = list()
    for i in range(4):
        x = r + dx[i] * l
        y = c + dy[i] * l
        temp.append(dac(x, y, l // 2))
    temp.sort()
    return temp[-2]

print(dac(0, 0, n // 2))

 

 

풀이

- 각 범위를 2로 나누어 가면서 분할정복을 실시한다.

- 기준점에 대하여 4가지로 나누기 때문에 dx, dy를 통해 좌표의 방향성을 정하고, 그 길이( l )를 곱함으로써 기준점을 분할한다.

- 이후에 리스트를 생성하여 인덱싱을 통해 두 번째 수를 구한 후 리턴 및 정복 과정을 거쳐 정답을 도출한다.

 

 

알게된 점

- 분할정복을 활용해서 이렇게 하면 되겠지 했는데 바로 정답이 떠서 조금 당황했떤 문제였다.

 

 

참고 사이트

-