BOJ 1780 종이의 개수

https://www.acmicpc.net/problem/1780
시간 2초, 메모리 256MB
input :

• N(1 ≤ N ≤ 3^7, N은 3k 꼴)
• N개의 정수로 행렬이 주어

output :

• -1로만 채워진 종이의 개수
• 0으로만 채워진 종이의 개수
• 1로만 채워진 종이의 개수

---

맨 처음 부터 길이가 1일 때와 n 일때 부터 세아리면서 시작했어야 하는데 이 둘을 빼먹는 바람에 시간을 좀 썼다..

다른 사람들의 풀이를 보니 다들 현재 확인 하는 범위에서 target 과 다른 값이 나오면
그 안에서 9개의 칸으로 나눈 다음

for i in range(0, 3):
    for j in range(0, 3):

처럼 나누는 경우가 많았다..

나는 그냥 while 문에서 3의 제곱승을 지정 해두고. 확인이 된 부분이라면 2로 업데이트를 해서 visit과 같은 역할을 할 수 있도록 하게 했다.

나중에는 python으로 풀 수 있도록 업데이트 해야 겠다.

import sys

n = int(sys.stdin.readline())
graph = []
top = 0
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

temp = n
while temp > 1:
    temp //= 3
    top += 1

def check(x, y, target, move):
    for i in range(x, x + move):
        for j in range(y, y + move):
            if graph[i][j] != target:
                return False
    return True

def twos(x, y, move):
    for i in range(x, x + move):
        for j in range(y, y + move):
            graph[i][j] = 2


zeros = 0
ones = 0
minuses = 0

while top >= 0:
    move = 3 ** top
    for x in range(0, n, move):
        for y in range(0, n, move):
            if graph[x][y] == 2:
                continue
            if check(x, y, graph[x][y], move):
                if graph[x][y] == 0:
                    zeros += 1
                elif graph[x][y] == 1:
                    ones += 1
                else:
                    minuses += 1
                twos(x, y, move)
    top -= 1
print(minuses)
print(zeros)
print(ones)