문제
2630번: 색종이 만들기
아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2 k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.
https://www.acmicpc.net/problem/2630
아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.
전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.
전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.
위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.
입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다.
- N은 2, 4, 8, 16, 32, 64, 128 중 하나이다.
- 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
- 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.
출력
- 첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.
풀이
- 자주 나오는 분할정복+재귀 문제이다. Class 3에서는 주로 분할정복, 완전탐색, DP가 나오는 것 같다.
- 색종이를 4등분하는 것으로 4개로 잘라 확인하고 아니면 문자열 형태로 더해서 반환하는식으로 구현했다.
설명
- 해당 함수를 재귀로 사용할 것이기때문에
n의 크기가1인지 부터 확인하는 조건으로 시작한다.
1이 아니라면 4개로 분할해 크기를 1/4 (길이는 1/2)로 줄이고 시작 점이 되는x와y를 더해 재귀함수를 호출한다.
- 호출된 함수의 결과가 4개 모두 같고 길이가 1이라면 해당 종이는 한가지 색으로 구성된 것이므로 그대로 반환한다.
- 아니라면 한조각이라고 다르다는 의미이므로 각 결과를 더해서 반환한다.
- 처음에 입력을 받을때 숫자로 받지 않고 그냥
split만 사용해 문자로 받은 이유가 값을 반환할때 더해서 넘겨주는 편이 코드도 짧고 간편할 것이라고 생각했기 때문이다.
답
from sys import stdin
input = stdin.readline
def making_colored_paper(n, cp, x, y):
if n == 1:
return cp[x][y]
cp1 = making_colored_paper(n // 2, cp, x, y)
cp2 = making_colored_paper(n // 2, cp, x, y + n // 2)
cp3 = making_colored_paper(n // 2, cp, x + n // 2, y)
cp4 = making_colored_paper(n // 2, cp, x + n // 2, y + n // 2)
if cp1 == cp2 == cp3 == cp4 and len(cp1) == 1:
return cp1
return cp1+cp2+cp3+cp4
if __name__ == "__main__":
N = int(input())
paper = [input().split() for _ in range(N)]
res = making_colored_paper(N, paper, 0, 0)
print(res.count('0'), res.count('1'), sep='\n')
Uploaded by Notion2Tistory v1.1.0