백준 1780번: 종이의 개수

[www.acmicpc.net/problem/1780]

#풀이
- 분할 정복문제 이다. 분할 정복은 세가지 구성요소가 있다.

• 작은 문제로 분할하는 과정(divid)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
• 더이상 답을 분할하지 않고 풀 수 있는 작은 문제(base case)

1. 제일 작은 문제에서 종이의 개수가 9이면 종이의 개수는 1개이다.

2. 병합 과정에서 두 개의 종이의 개수가 0이면 종이의 개수는 1개이다.

위처럼 예외처리에 유의해서 코드를 짜면 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

import sys from math import gcd input = lambda : sys.stdin.readline().rstrip()   N=int(input()) data=[list(map(int,input().split())) for _ in range(N)]   def divid(arr):     a=b=c=0     l=len(arr)     #base case     if l == 3:         for i in range(3):             for j in range(3):                 if arr[i][j] == -1:                     a+=1                 elif arr[i][j] == 0:                     b+=1                 else:                     c+=1         if(a==9 or b ==9 or c==9):             return a%8,b%8,c%8         return a,b,c          for i in range(0,l,l//3):         #divid         for j in range(0,l,l//3):             tmp=[]             for k in range(l//3):                 tmp.append(arr[i+k][j:j+l//3])             tmp1,tmp2,tmp3=divid(tmp)             #merge             a+=tmp1             b+=tmp2             c+=tmp3     if(a+b==0 or b+c==0 or a+c==0):         return a%8,b%8,c%8     return a,b,c   for i in divid(data):     print(i) Colored by Color Scripter

cs