해킹왕 양선규

분할 정복 문제이다. 접근 순서가 작은 문제에서 큰 문제이든 큰 문제에서 작은 문제이든, 결국 작은 문제의 해결 방식이 큰 문제의 해결로 이어진다면 그것은 분할 정복이라고 할 수 있다. 매우 까다롭고 헷갈리는 문제였다.  # 분할 정복import sysinput = sys.stdin.readlineN = int(input())start = ['***', '* *', '***'] # N이 3일 경우의 초기 모양def divideAndConquer(num, star):    # 종료 조건    if num == N:        return star        """    이 반복문은 기존 star를 그대로 출력하는 것을 의미한다.    따라서 3배 곱하여 append해주면 옆으로 3배 늘리는 것이 된다...

# 정사각형 한 변의 길이 : 2, 4, 8 ....import sysinput = sys.stdin.readline# 2의 N승 크기, R행 C열N, R, C = map(int, input().split())# 행/열이 길이 나누기 2이상이면 -> 행 : 아래쪽 사분면/ 열 : 오른쪽 사분면le = 2**N# 결과값 편하게 더하기 위해 만든 배열num = [[0,1], [2,3]]# 각사분면 0,0값, 변길이, 행, 열def divide(z, le, row, col):    if le == 2: # 2*2 정사각형 도달 시        print(z + num[row][col])        return    plus = (le * le) // 4 # 각 사분면 0,0 값의 차이    half = le..

분할 정복 문제이다. N * N 형태의 좌석과 추첨번호가 주어진다.여기서 N은 2의 0승 ~ 2의 10승 중 하나이고, 따라서 정사각형 형태이며 4등분으로 분할이 가능하다. 특별상은 딱 한명만 받을 수 있다.사람이 1명밖에 없다면 그 사람이 수상한다.사람이 4명이라면(N : 2) 4명 중 추첨번호가 2번째로 작은 사람이 수상한다.사람이 16명(N : 4) 이상이라면, 각 구역에 사람이 4명만 남을 때까지 4등분한 후, 각 구역마다 2번째로 작은 사람을 가려내고, 그렇게 추려진 사람들 중에서 또 2번째로 작은 사람을 가려내고.. 하는 형태로 진행한다.  위 그림에선 왼쪽 위 : 1 , 오른쪽 위 : 3, 왼쪽 아래 : 5, 오른쪽 아래 : 7 이다.이렇게 추첨된 1, 3, 5, 7 중에서 또 2번째로 작은..

n = int(input()) # 변의 길이 board = [list(map(int, input().rstrip())) for _ in range(n)] # rstrip() 하면 개행문자 제거해서 한번에 입력할 수 있게 해준다 def quadTree(x, y, n): # x, y좌표와 변 길이를 입력받는다, 첫 호출은 0,0을 입력 color = board[x][y] for i in range(x, x+n): for j in range(y, y+n): # 현재 사각형의 모든 칸을 검사한다 if color != board[i][j]: # 색깔이 다른 칸이 하나라도 있다면 4등분 재귀호출 한다 print('(', end='') # 출력 양식에 맞게 괄호 입력 quadTree(x, y, n//2) # 출력 양..

import sys n = int(sys.stdin.readline()) # 종이 길이 paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] # 종이와 색깔 result = [] # 결과를 담을 변수 def cut(x, y, n): # 행, 열 시작지점과 종이 길이를 입력받는다 color = paper[x][y] # 종이 색깔 비교를 위한 색깔 저장 for i in range(x, x + n): for j in range(y, y + n): if color != paper[i][j]: # 다른 색깔이 존재할 경우 종이를 4등분한다 cut(x, y, n//2) cut(x+n//2, y, n//2) cut(x, y+n//2, n//..