백준 1780번 종이의 개수

백준 1780번 종이의 개수 문제이다.

 

문제는 다음과 같다. 

 

이전 색종이 만들기 문제와 유사하다.

https://certangsecurity.tistory.com/148

백준 2630번 색종이 만들기

4등분이었던 것이 9등분이 되었고 색깔의 종류가 2가지에서 3가지로 늘었다고 생각하면 될 것 같다.

이전 코드에서 바뀐부분만 수정하여 제출했는데.. 시간초과가 나온다..

 

코드를 살펴보면 

import sys

ln = int(sys.stdin.readline().strip())
result = [0, 0, 0]
arr = []


def check(n, x, y):
    global result
    for i in range(n):
        for j in range(n):
            if arr[x][y] != arr[x+i][y+j]:
                return 0
    if arr[x][y] == -1:
        result[0] += 1
    elif arr[x][y] == 0:
        result[1] += 1
    else:
        result[2] += 1


def nemo(n, x, y):
    global result
    if n == 1:
        if arr[x][y] == -1:
            result[0] += 1
        elif arr[x][y] == 0:
            result[1] += 1
        elif arr[x][y] == 1:
            result[2] += 1
        return

    if check(n, x, y) == 0:
        for i in range(3):
            for j in range(3):
                nemo(n//3, i*n//3+x, j*n//3+y)


arr = [list(map(int, input().split())) for _ in range(ln)]


nemo(ln, 0, 0)
for i in range(3):
    print(result[i])

 

이전에는 잘라진 부분을 따로 배열로 받아 처리를 했다면

여기서는 시간을 줄이기 위해 자를 필요 없이 전체의 배열에서 해당 부분만 살펴보는 식으로 바꾸었다. 

또한 잘라진 부분의 원소들의 값을 모두 보고 같다면 1장으로 처리하는 것이 아닌 

첫번째 값과 나머지값을 차례로 비교하면서 다르다면 바로 나누는 함수로 넘기도록 바꾸었다. 

시간적으로 크게 차이 없을 것 같은데 정답과 시간초과로 나뉘었다. 

 

많은 시도끝에 성공!