[BOJ] 2630. 색종이 만들기

문제

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

• 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하기

 

---

주요 아이디어

• 영역 전체가 같은 색이 아니라면 절반으로 계속 잘라주기 -> 재귀로 구현
• 파란색 / 하얀색 종이 판단해서 cnt 올리기

---

 

코드 구현 (Python 3)

 

import sys
from collections import Counter
sys.setrecursionlimit(10**5)

result = []

# 색종이의 color 판단
def check_color(paper):
    total = sum(sum(paper, []))
    if total == len(paper) * len(paper[0]):
        return 'B'
    elif total == 0:
        return 'W'
    else:
        return None
    

def recursive_cut(paper):
    global result
    paper_color = check_color(paper)

    # 4분할 하기
    if paper_color == None:
        r_mid = len(paper) // 2
        c_mid = len(paper[0])//2

        # 좌상단
        recursive_cut([row[:c_mid] for row in paper[:r_mid]])
        # 우상단
        recursive_cut([row[c_mid:] for row in paper[:r_mid]])
        # 좌하단
        recursive_cut([row[:c_mid] for row in paper[r_mid:]])
        # 우하단
        recursive_cut([row[c_mid:] for row in paper[r_mid:]])

    # 분할된 경우
    else:
        result.append(paper_color)

N = int(input())
paper = [[int(i) for i in sys.stdin.readline().split()] for r in range(N)]
recursive_cut(paper)
counter = Counter(result)
print(counter['W'])
print(counter['B'])

 

 

---

 

제출 결과