[ BOJ 1780 ] 종이의 개수(Python)

uoayop·2021년 6월 1일
0

알고리즘 문제

목록 보기
78/103
post-thumbnail

문제

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

[BOJ 2630] 색종이 만들기 문제와 동일하다.
종이를 1/9로 줄여준다고 생각하면 된다.


문제 풀이

0. 입력 받기

n = int(input())
minus_cnt, zero_cnt, plus_cnt = 0, 0, 0

papers = []
for _ in range(n):
    row = list(map(int, input().rsplit()))
    papers.append(row)

1. 현재 종이 색상과 다르면 분할하기

# 현재 종이 색상
curr = papers[row][col]

for i in range(row, row + n):
    for j in range(col, col + n):
        if papers[i][j] != curr:
            # 다음 종이의 길이는 1/3
            next_n = n // 3
            
            check(row, col, next_n)  # 1
            check(row, col + next_n, next_n)  # 2
            check(row, col + (2 * next_n), next_n)  # 3
            check(row + next_n, col, next_n)  # 4
            check(row + next_n, col + next_n, next_n)  # 5
            check(row + next_n, col + (2 * next_n), next_n)  # 6
            check(row + (2 * next_n), col, next_n)  # 7
            check(row + (2 * next_n), col + next_n, next_n)  # 8
            check(row + (2 * next_n), col + (2 * next_n), next_n)  # 9
            return

2. 현재 종이 색상에 따라 갯수 세어주기

if curr == -1:
    minus_cnt += 1
elif curr == 0:
    zero_cnt += 1
elif curr == 1:
    plus_cnt += 1
return

코드

import sys
input = sys.stdin.readline

n = int(input())
minus_cnt, zero_cnt, plus_cnt = 0, 0, 0

papers = []
for _ in range(n):
    row = list(map(int, input().rsplit()))
    papers.append(row)


def check(row, col, n):
    global minus_cnt, zero_cnt, plus_cnt
    curr = papers[row][col]

    for i in range(row, row + n):
        for j in range(col, col + n):
            if papers[i][j] != curr:
                next_n = n // 3
                check(row, col, next_n)  # 1
                check(row, col + next_n, next_n)  # 2
                check(row, col + (2 * next_n), next_n)  # 3
                check(row + next_n, col, next_n)  # 4
                check(row + next_n, col + next_n, next_n)  # 5
                check(row + next_n, col + (2 * next_n), next_n)  # 6
                check(row + (2 * next_n), col, next_n)  # 7
                check(row + (2 * next_n), col + next_n, next_n)  # 8
                check(row + (2 * next_n), col + (2 * next_n), next_n)  # 9
                return

    if curr == -1:
        minus_cnt += 1
    elif curr == 0:
        zero_cnt += 1
    elif curr == 1:
        plus_cnt += 1
    return


check(0, 0, n)

print(minus_cnt)
print(zero_cnt)
print(plus_cnt)
profile
slow and steady wins the race 🐢

0개의 댓글