❓문제
https://www.acmicpc.net/problem/2630
❗문제 정리
분할 정복 : 문제를 작은 문제로 분할하여, 분할한 작은 문제들을 해결하고, 작은 문제에 대한 결과를 원본 문제에 대한 결과로 조합.
function F(x):
if F(x)의 문제가 간단한 경우:
return F(x)를 직접 계산한 값
else:
x를 x1, x2로 분할.
f(x1), f(x2)풀기
return f(x1), f(x2)📑코드
n=int(input())#종이 한 변의 길이
paper=[]
for _ in range(n):
paper.append(list(map(int,input().split())))
white, blue=0,0#흰색종이 세기, 파란색 종이 세기
def make_one_color_paper(num, paper):
#재귀인데 누적시켜야 하므로 global 변수 사용
global white
global blue
check=0
for i in range(num):
check+=sum(paper[i])
if check==0:#전체 종이가 흰색일 경우 전체 종이의 합이 0
white+=1
elif check==num*num:#전체 종이가 파란색일 경우 전체 종이의 합이 =종이 전체 크기
blue+=1
else:#아닌 경우 반씩 분할하기
tmp_paper=[paper[i][0:num//2] for i in range(0,num//2)]
make_one_color_paper(num//2, tmp_paper)
tmp_paper=[paper[i][0:num//2] for i in range(num//2,num)]
make_one_color_paper(num//2, tmp_paper)
tmp_paper=[paper[i][num//2:num] for i in range(0,num//2)]
make_one_color_paper(num//2, tmp_paper)
tmp_paper=[paper[i][num//2:num] for i in range(num//2,num)]
make_one_color_paper(num//2, tmp_paper)
make_one_color_paper(n, paper)
print(white)
print(blue)📝코드 설명
n=int(input())#종이 한 변의 길이
paper=[]
for _ in range(n):
paper.append(list(map(int,input().split())))정사각형 종이 한변의 길이 n과 종이 paper를 입력받는다.
white, blue=0,0#흰색종이 세기, 파란색 종이 세기흰색종이의 개수를 white, 파란색종이의 개수를 blue에 저장하기 위해 0으로 초기화한다.
def make_one_color_paper(num,paper)
global white
global blue
check=0분할정복이므로 재귀로 풀어야한다. 이때, white, blue는 값을 누적시켜야하는 변수이므로 재귀로인해 값이 초기화 되지 않도록 global 변수 사용햔다.
for i in range(num):
check+=sum(paper[i])전체 종이가 한가지 색으로 이루어졌는지의 여부를 판단하기 위한 check변수를 생성한다. 모든 종이의 값을 더하는 것이다.
if check==0:#전체 종이가 흰색일 경우 전체 종이의 합이 0
white+=1
elif check==num*num:#전체 종이가 파란색일 경우 전체 종이의 합이 =종이 전체 크기
blue+=1모든 종이의 값을 합한 check가 0이면 종이1장이 전부 흰색이라는 것이므로 white+1, check가 num*num의 크기를 가지면 종이 1장이 파란색이라는 것이므로 blue+1한다.
else:#아닌 경우 반씩 분할하기
tmp_paper=[paper[i][0:num//2] for i in range(0,num//2)]
make_one_color_paper(num//2, tmp_paper)
tmp_paper=[paper[i][0:num//2] for i in range(num//2,num)]
make_one_color_paper(num//2, tmp_paper)
tmp_paper=[paper[i][num//2:num] for i in range(0,num//2)]
make_one_color_paper(num//2, tmp_paper)
tmp_paper=[paper[i][num//2:num] for i in range(num//2,num)]
make_one_color_paper(num//2, tmp_paper)여러 색상이 섞여 있을 경우, 크기를 반씩 나누어서 다시 종이의 개수를 세는 함수를 반복한다.
🎖제출 결과
💡insight
AI dev