230. 색종이 만들기

1) 어떤 전략(알고리즘)으로 해결?

• 분할 정복

2) 코딩 설명

<내 풀이>

import sys
n = int(sys.stdin.readline().strip())
paper = []
white = 0
blue = 0
for i in range(n) : 
    paper.append(list(map(int, sys.stdin.readline().rstrip().split())))

# 여기로 보내진 애들은 합이 안맞는 애들의  쪼개짐 후보들
def recur(r,c, width) :
    global white
    global blue
    
    if all_same_color(r,c,width)==True: 
        if paper[r][c] ==0 : 
            white+=1
        else : 
            blue+=1
        return

    else : 
        # print(r,c,n//2)
        recur(r,    c,      width//2)
        recur(r,    c+width//2,     width//2)
        recur(r+width//2,   c,      width//2)
        recur(r+width//2,   c+width//2,     width//2)
        return
#####################################

def all_same_color(r,c, width) :
    cnt = 0
    summ = 0
    for rr in range(r,r+width) : 
        for cc in range(c,c+width) : 
            cnt+=1
            summ+= paper[rr][cc]
    return (summ == cnt or summ==0)

#######################################

recur(0,0,n)
print(white)
print(blue)

< 내 틀렸던 풀이, 문제점>

재귀가 안 멈춰!

import sys

n = int(sys.stdin.readline().strip())
paper = []
white = 0
blue = 0
for i in range(n) : 
    paper.append(list(map(int, sys.stdin.readline().rstrip().split())))

# 여기로 보내진 애들은 합이 안맞는 애들의  쪼개짐 후보들
def recur(r,c, width) :
    global white
    global blue

    if width == 0 : 
        return
    if all_same_color(r,c,width) : 
        if paper[r][c] ==0 : white+=1
        else : blue+=1
        return
    else : 
            recur(r,    c,      n//2)
            recur(r,    c+n//2,     n//2)
            recur(r+n//2,   c,      n//2)
            recur(r+n//2,   c+n//2,     n//2)
#####################################

def all_same_color(r,c, width) :
    cnt = 0
    summ = 0
    for rr in range(r,r+width) : 
        for cc in range(c,c+width) : 
            cnt+=1
            summ+= paper[rr][cc]
    return (summ == cnt or summ==0)

#######################################

if all_same_color(0,0,n) : #원큐에 됨
    if paper[0] == 0 : #하양이었으면
        print(1)
        print(0)
    else : 
        print(0)
        print(1)
########################################

else : 
    recur(0,0,n//2)
    recur(0,n//2,n//2)
    recur(n//2,0,n//2)
    recur(n//2,n//2,n//2)

    print(white)
    print(blue)

import sys
n = int(sys.stdin.readline().strip())
paper = []
white = 0
blue = 0
for i in range(n) : 
    paper.append(list(map(int, sys.stdin.readline().rstrip().split())))

# 여기로 보내진 애들은 합이 안맞는 애들의  쪼개짐 후보들
def recur(r,c, width) :
    global white
    global blue
    
    if all_same_color(r,c,width)==True: 
        if paper[r][c] ==0 : 
            white+=1
        else : 
            blue+=1
        return

    else : 
        # print(r,c,n//2)
        recur(r,    c,      n//2)
        recur(r,    c+n//2,     n//2)
        recur(r+n//2,   c,      n//2)
        recur(r+n//2,   c+n//2,     n//2)
        return
#####################################

def all_same_color(r,c, width) :
    cnt = 0
    summ = 0
    for rr in range(r,r+width) : 
        for cc in range(c,c+width) : 
            cnt+=1
            summ+= paper[rr][cc]
    return (summ == cnt or summ==0)

#######################################

recur(0,0,n)
#print(all_same_color(0,0,n//2))

print(white)
print(blue)

뜨악~~ recur 함수에서,,, width 자리에 n 을 넣었었다... 어쩐지 길이가 줄어들어야 하는데 안 줄어들고 ㅠㅠㅠㅠ 그랬는데 흑흑

아래는 시간초과

• 당연하지! 체크 배열에서 하낳나ㅏ 체크하고앉아있어서..

import sys
n = int(sys.stdin.readline().strip())
paper = []
white = 0
blue = 0
for i in range(n) : 
    paper.append(list(map(int, sys.stdin.readline().rstrip().split())))
check = []
# 여기로 보내진 애들은 합이 안맞는 애들의  쪼개짐 후보들
def recur(r,c, width) :

    global check
    global paper
    global white
    global blue

    #print("before " , r,c,width)
    
    if all_same_color(r,c,width) : 
        if paper[r][c] ==0 : 
            white+=1
        else : 
            blue+=1
        return

    else : 
        #print(check)
        if ((r,c,width//2) not in check) : 
            check.append((r,c,width//2))
            recur(r,    c,      width//2)
            
        if ((r,    c+width//2,     width//2) not in check) : 
            check.append((r,    c+width//2,     width//2))
            recur(r,    c+width//2,     width//2)
            
        if((r+width//2,   c,      width//2) not in check) : 
            check.append((r+width//2,   c,      width//2))
            recur(r+width//2,   c,      width//2)
            
        if((r+width//2,   c+width//2,     width//2) not in check) : 
            check.append((r+width//2,   c+width//2,     width//2))
            recur(r+width//2,   c+width//2,     width//2)
            
        return
#####################################

def all_same_color(r,c, width) :
    cnt = 0
    summ = 0
    #print(r,c,width)
    for rr in range(r,r+width) : 
        for cc in range(c,c+width) : 
            cnt+=1
            #print(rr,cc)
            summ+= paper[rr][cc]
    return (summ == cnt or summ==0)

#######################################

recur(0,0,n)

print(white)
print(blue)

<반성 점>

<배운 점>