BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/1780
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수
www.acmicpc.net
내가 작성한 코드
import sys
read = sys.stdin.readline
def read_data():
N = int(read().rstrip())
paper = []
for _ in range(N):
paper.append(list(map(int, read().rstrip().split())))
return N, paper
def count(N, i, j, paper):
tmp = paper[i][j]
for r in range(i, i+N):
for c in range(j, j+N):
if paper[r][c] != tmp:
return False, 0, 0, 0
if tmp == -1:
return True, 1, 0, 0
if tmp == 0:
return True, 0, 1, 0
return True, 0, 0, 1
def recursion(N, i, j, paper):
done, minus, zero, plus = count(N, i, j, paper)
if done:
return minus, zero, plus
n = N // 3
for nw_i in range(i, i+N, n):
for nw_j in range(j, j+N, n):
m, z, p = recursion(n, nw_i, nw_j, paper)
minus, zero, plus = minus+m, zero+z, plus+p
return minus, zero, plus
N, paper = read_data()
for n in recursion(N, 0, 0, paper):
print(n)
- 재귀
- 현재 모든 값이 동일하면 return
- 아니면 9등분하여 recursion
다른 사람이 작성한 코드
import sys
N = int(sys.stdin.readline())
matrix = []
result = [0] * 3
for _ in range(N):
matrix.append(list(map(int, sys.stdin.readline().split())))
def check(start_x: int, start_y: int, n: int):
temp = matrix[start_x][start_y]
for i in range(n):
for j in range(n):
if temp != matrix[start_x + i][start_y + j]:
return False
return True
def divide(start_x: int, start_y: int, n: int):
if check(start_x, start_y, n):
result[matrix[start_x][start_y] + 1] += 1
else:
for i in range(3):
for j in range(3):
divide(start_x + i* n//3, start_y + j* n//3, n//3)
return
divide(0, 0, N)
for i in range(3):
print(result[i])
- 위 코드를 참고
- 내 코드랑 똑같아보이는데 이 코드는 통과하는지 확인하기 위해 사용
[백준알고리즘] 1780번: 종이의 개수 -Python
[백준알고리즘] 1780번: 종이의 개수 -Python https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어..
suri78.tistory.com
기억해야할 것
- Pruning
- 재귀가 발생하면 counting을 처음부터 다시함
- 따라서, 재귀 조건이 되면 counting을 멈춰야함
- List slicing
- 리스트 슬라이싱으로 시간초과
- 인덱스도 헷갈림
- 이 문제로 너무 오래 걸렸음... 재귀 문제를 많이 풀어야 할듯
'코딩테스트' 카테고리의 다른 글
[백준][재귀] Choose Your Own Arithmetic (0) | 2022.04.01 |
---|---|
[백준][슬라이딩윈도우] 달려라 홍준 (0) | 2022.03.29 |
[백준][세그먼트트리] 최솟값과 최댓값 (0) | 2022.03.23 |
[백준][누적합] 나머지 합 (0) | 2022.03.22 |
[프로그래머스] 다리를 지나는 트럭 (0) | 2022.03.12 |