acmicpc.net 1992(분할 정복), 11729(분할 정복), 1780(분할 정복)

https://www.acmicpc.net/problem/1992

4개로 분할하여 푼다.

# -*- encoding: cp949 -*-
import sys
def quad(x1, y1, x2, y2):
    flag = False
    #print 'h =',x1,y1,x2,y2,
    for i in xrange(y1, y2+1):
        for j in xrange(x1, x2+1):
            if maps[y1][x1] != maps[i][j]:
                flag = True
                break
        if flag: break
    if not flag:
        #print 'here =',x1,y1,maps[y1][x1]
        sys.stdout.write(maps[y1][x1])
    if flag:
        h_x = (x1+x2)/2; h_y = (y1+y2)/2
        sys.stdout.write('(')
        quad(x1, y1, h_x, h_y)
        quad(h_x+1, y1, x2, h_y)
        quad(x1, h_y+1, h_x, y2)
        quad(h_x+1, h_y+1, x2, y2)
        sys.stdout.write(')')

n = input()
maps = [list(raw_input()) for i in xrange(n)]
quad(0,0,n-1,n-1)

https://www.acmicpc.net/problem/11729

유명한 하노이 탑 문제.

# -*- encoding: cp949 -*-
def hanoi(k,start,mid,end):
    if k==1:
        print start,end
    else:
        hanoi(k-1,start,end,mid)
        print start,end
        hanoi(k-1,mid,start,end)

k = input()
print 2**k-1
hanoi(k,1,2,3)

https://www.acmicpc.net/problem/1780

맨 위의 1992번 문제와 비슷하긴 한데 짜증난다.

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(10000000)
def cut(x1, y1, x2, y2, depth):
    flag = False
    for i in xrange(y1+1, y2+1):
        for j in xrange(x1+1, x2+1):
            if arr[y1+1][x1+1] != arr[i][j]:
                flag = True
                break
        if flag: break
    if not flag:
        paper[arr[y1+1][x1+1]] += 1
    if flag:
        if y2-y1==3 and x2-x1==3:
            for i in xrange(y1+1,y2+1):
                for j in xrange(x1+1,x2+1):
                    paper[arr[i][j]] += 1
        else:
            t_x = (x2-x1)/3; t_y = (y2-y1)/3
            cut(x1,         y1, x1 + t_x,    y1 + t_y, depth+1)
            cut(x1 + t_x,   y1, x1 + t_x*2,  y1 + t_y, depth+1)
            cut(x1 + t_x*2, y1, x2,          y1 + t_y, depth+1)
  
            cut(x1,         y1 + t_y,  x1 + t_x,    y1 + t_y*2, depth+1)
            cut(x1 + t_x,   y1 + t_y,  x1 + t_x*2,  y1 + t_y*2, depth+1)
            cut(x1 + t_x*2, y1 + t_y,  x2,          y1 + t_y*2, depth+1)
  
            cut(x1,         y1 + t_y*2,  x1 + t_x,   y2, depth+1)
            cut(x1 + t_x,   y1 + t_y*2,  x1 + t_x*2, y2, depth+1)
            cut(x1 + t_x*2, y1 + t_y*2,  x2,         y2, depth+1)
  
n = input()
arr = [[999]*n] + [[999] + map(int,raw_input().split())for i in xrange(n)]
paper = [0 for i in range(3)]
cut(0,0,n,n,0)
print paper[-1],'\n',paper[0],'\n',paper[1]