애매한 차이. (#1780 종이의 개수)

#1780번 종이의 개수 https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

평범한 분할정복 문제라고 생각하고 열심히 짰다.

 

틀린코드

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
answer = [0, 0, 0]  # 0, 1, -1


def check(mat):
    pivot = None
    for r in mat:
        for c in r:
            if pivot:
                if pivot != c:
                    return False
            else:
                pivot = c

    return True


def solve(mat, N):
    # n =  sqrt(n)
    n = N//3
    # 나눠서 재귀호출
    if not check(mat):
        for y in range(3):
            for x in range(3):
                submat = [r[n*x:n*(x+1)]
                          for r in mat[n*y:n*(y+1)]]
                solve(submat, n)
    else:
        answer[mat[0][0]] += 1


solve(matrix, N)
print(answer[-1])
print(answer[0])
print(answer[1])

근데 자꾸 틀려서 짜증났다.

아무래도 인덱스를 조절하는 방법에서 문제가 있었던 것 같다.

위와 같이 리스트를 잘라서 적용하는 방법보다는

인덱스 그 자체를 전달하는 방법이 더 효율적이라고 느꼈다. (다른 코드 참조함)

 

정답코드

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
answer = [0, 0, 0]  # 0, 1, -1


def check(x, y, n):
    pivot = matrix[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if pivot != matrix[i][j]:
                return True
    return False


def solve(x, y, n):
    if check(x, y, n):
        for dy in range(3):
            for dx in range(3):
                solve(x+dx*n//3, y+dy*n//3, n//3)
        return
    else:
        answer[matrix[x][y]] += 1


solve(0, 0, N)
print("{}\n{}\n{}".format(answer[-1], answer[0], answer[1]))

훨씬 깔끔하고 직관적인 코드가 됐다.