Algorithm/acmicpc.net
애매한 차이. (#1780 종이의 개수)
winney916
2022. 3. 15. 00:19
728x90
#1780번 종이의 개수 https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
평범한 분할정복 문제라고 생각하고 열심히 짰다.
틀린코드
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]))
훨씬 깔끔하고 직관적인 코드가 됐다.