BOJ 백준 17829번 222-풀링 | Python
🔎 문제 설명
🩶 실버 2
- 난이도 ★★★☆
- 분할정복
전공 수업에서 CNN 합성곱 계산을 했던 기억이…ㅎ
일단 문제 설정이 너무 웃펐다. 특히 마지막 문장…🫠
랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.
🚀 힌트
이 문제를 풀면서 느꼈는데 이게 가장 큰 힌트다. 잊지 말자!!
분할정복은 큰 문제를 작은 문제로 분할하여 해결하는 방법이다.
📌 문제 풀이 큰 틀은 다음과 같다.
- 각 2 x 2 사각형에서 두 번째로 큰 숫자만 뽑아와서 임시 리스트로 저장
- 1 x 1이 될 때까지 반복
💻 내 코드
import sys
input = sys.stdin.readline
N = int(input())
squares = []
for _ in range(N):
squares.append(list(map(int, input().split())))
def solution(x, y, n):
if n == 2:
answer = [squares[x][y], squares[x+1][y], squares[x][y+1], squares[x+1][y+1]]
answer.sort()
return answer[-2]
lu = solution(x, y, n//2)
ld = solution(x+n//2, y, n//2)
ru = solution(x, y+n//2, n//2)
rd = solution(x+n//2, y+n//2, n//2)
answer = [lu, ld, ru, rd]
answer.sort()
return answer[-2]
answer = solution(0,0,N)
print(answer)
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).