![[2630번] 색종이 만들기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FHpFKC%2FbtqwCrk76tf%2FKQsqdOlW2IEY52tl9PWZWK%2Fimg.png)
반응형
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.
www.acmicpc.net
가장 기본적인 Divide-&-Conquer(분할 정복) 문제 중 하나라고 할 수 있습니다.
한 변의 길이가 $2^n$인 정사각형을 입력받은 후에 정확히 4등분을 해서 온전히 0 또는 1로 이루어진 색종이를 얻습니다.
그리고 0으로만 이루어진 색종이와 1로만 이루어진 색종이의 개수를 각각 세기만 하면 됩니다.
'분할 정복'인 만큼 재귀 함수를 다루는 실력이 필요하겠죠?
이번 문제를 통해 분할 정복을 시작해보도록 합시다!
반응형