문제
<예제>
8 9 하얀색 카드 수
1 1 0 0 0 0 1 1 7 파란색 카드 수
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
나의 풀이
1. 2번째 줄부터 차례대로 받아 행렬을 s에 저장한다.
2. 행렬의 1의 개수와 0의 개수를 count
3. cnt == (N-f)^2이면 모두 같은 수로 이루어져 있으므로 멈춤
아니라면 4구역으로 나눠서 재귀 함수
4. 1로 이루어져 있으면 blue +1
0으로 이루어져 있으면 white +1
def recs(s, f, N, ff, M):
global blue, white
cnt = 0
cnt_1 = 0
for i in range(f, N): # 첫번째 범위
for j in range(ff, M): # 두번째 범위
if s[i][j] == 0:
cnt += 1
else:
cnt_1 += 1
if cnt == (N - f) ** 2: # 0과 1의 개수가 전체와 같다면
white += 1
elif cnt_1 == (N - f) ** 2:
blue += 1
else: # 아니라면 재귀
recs(s, f, (N+f)//2, ff, (M+ff)//2) # 2사분면 2 | 1
recs(s, f, (N+f)//2, (M+ff)//2, M) # 1사분면 3 | 4
recs(s, (N+f)//2, N, ff, (M+ff)//2) # 3사분면
recs(s, (N+f)//2, N, (M+ff)//2, M) # 4사분면
N = int(input())
s = [list(map(int, input().split())) for _ in range(N)] # 행렬 채우기
blue = 0
white = 0
recs(s, 0, N, 0, N)
print(white)
print(blue)
- 초반에 첫번째 범위와 두번째 범위의 변수명을 헷갈리게 줘서 범위선정에 시간이 걸렸다.
- 재귀의 활용은 확실히 깨닫고나니 어떻게해서든 문제는 풀어냈다.
- 간략한 풀이도 아니고 변수명과 범위설정도 무작정이라 더욱 좋은 풀이를 찾아봐야겠다.
다른 풀이
import sys
N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
result = []
def solution(x, y, N):
color = paper[x][y]
for i in range(x, x+N):
for j in range(y, y+N):
if color != paper[i][j]:
solution(x, y, N//2)
solution(x, y+N//2, N//2)
solution(x+N//2, y, N//2)
solution(x+N//2, y+N//2, N//2)
return
if color == 0 :
result.append(0)
else :
result.append(1)
solution(0,0,N)
print(result.count(0))
print(result.count(1))
# 4x4 행렬을 가정하면 범위 (x, x+N) (y, y+N)
# sol(0, 0, 4) -> sol(0, 0, 2) (0, 2) (0, 2)
# -> sol(0, 2, 2) (0, 2) (2, 4)
# -> sol(2, 0, 2) (2, 4) (0, 2)
# -> sol(2 ,2, 2) (2, 4) (2, 4)- 처음 색을 구하고 그 색과 다르면 재귀를 실행시켰다
- 범위 변수를 잘 잡았다(정사각행렬임을 잘 사용)
Yeonju