[Python/코테] 백준 17829 222-풀링

17829 222-풀링

문제 및 조건 설명: https://www.acmicpc.net/problem/17829

알고리즘 설계

💡idea.

주어진 행렬의 한 변의 길이는 항상 2의 거듭제곱 꼴이고, 2x2 정사각형으로 나눠야 한다.

단계별로 몇 개의 정사각형을 가지게 될 지 복잡하나, 단계별로 같은 동작을 반복하게 된다는 것을 알 수 있다.

즉 재귀로 풀 수 있다.

🎲step.

1. 함수

변의 길이가 2(즉 2x2 사각형)가 될 때까지 행렬을 쪼개고, 2x2일 때는 두 번째로 큰 값을 반환한다.

def func(x, y, size)		# x, y는 시작 좌표이고 size는 탐색할 부분의 한 변의 크기이다.

 

2. Base condition

size == 1일 때. 즉 한칸 * 한칸이 남았을 때

 

3.재귀

한 번에 2*2를 찾으려고 하기보다, 2*2가 나올 때까지 쪼갠다.

lt = func(x, y, size//2)
rt = func(x, y+size//2, size//2)
lb = func(x+size//2, y, size//2)
rb = func(x+size//2, y+size//2, size//2)
# lt, rt, lb, rb 중 두 번째로 큰 값을 반환한다.

알고리즘 구현

import sys

n = int(sys.stdin.readline().strip())
m = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


def pooling(x, y, size):
    if size == 2:
        answer = [m[x][y], m[x+1][y], m[x][y+1], m[x+1][y+1]]
        answer.sort(reverse=True)
        return answer[1]

    lt = pooling(x, y, size//2)
    rt = pooling(x, y+size//2, size//2)
    lb = pooling(x+size//2, y, size//2)
    rb = pooling(x+size//2, y+size//2, size//2)
    answer = [lt, rt, lb, rb]
    answer.sort(reverse=True)

    return answer[1]


print(pooling(0, 0, n))

출처: https://velog.io/@xx0hn/BOJ-Python-17829번-222-폴링

나다어

• 2 by 2 정사각형을 찾으려다가 생각이 꼬였다. 4등분하며 2 by 2가 나올 때까지 자르는 재귀적인 접근을 하자.
  단계별로, 절차지향적인 사고를 버리자!