문제
아래 <그림 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로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.
어떻게 풀 것이냐?
과정을 생략하고 풀이를 보고싶은 사람은 맨 아래로
접근방식 : N/2 x N/2의 문제로 나누어 생각하면 편하겠다!
NxN 의 정사각형에서 하나의 숫자로 이루어지지 않았다면?
→ N/2 x N/2 의 정사각형 4개로 쪼개서 다시 검사하자!
→ 재귀...? 라고 생각이 들었다.
재귀함수를 정의할 때 가장 중요하게 생각하는 것은
- 전달되는 파라미터
- 탈출조건
- 반환값의 유무
이다.
- 재귀함수의 파라미터로 반으로 짤린 정사각형의 2차원 배열을 전부 전달하기보다는 배열의 인덱스를 전달하는 것이 좋겠다.
배열의 인덱스를 전달하면 검사해야하는 정사각형의 크기를 알 수 없다! 크기가 필요하다.
- 탈출조건은 정사각형의 크기가 1일때!
- 파란색 종이🔷 와 흰색 종이 ⬜ 의 갯수를 반환하면 좋겠다고 생각했다.
일단은 이렇게 생각했다. 코딩을 하면서 바뀔 수 있겠다.
그럼 일단 입출력부터 정의해보자.
기본 입출력 정의
#include <iostream>
#include <vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin>>t;
//2차원 vector 동적 할당.
vector<vector<int>> v(t,vector<int>(t,0));
for(int i=0;i<t;i++) {
for (int j = 0; j < t; j++) {
cin >> v[i][j];
}
}
for(int i=0;i<t;i++) {
for (int j = 0; j < t; j++) {
cout<<v[i][j]<<" ";
}
cout<<"\n";
}
}vector로 입력받을까 array로 입력받을까 고민했는데
함수에 동적 2차원 배열을 전달하는 방법을 몰라서 vector로 선언.
vector가 편합니다...함수에 2차원 배열 전달 하는 법 몰라요 😭
재귀함수 정의
(파란색 종이🔷 의 갯수, 흰색 종이⬜ 의 갯수) 두개를 반환해야하니 pair<int,int>를 생각했다.
Parameter 로는 가로 인덱스, 세로 인덱스, 정사각형 사이즈, 2차원 배열 전체 를 전달받자!
🛑 여기서 잠깐! 🛑
원래는 재귀함수에서 파란색 종이🔷 의 갯수, 흰색 종이⬜ 의 갯수를 반환하고, 더해주는 재귀함수를 생각했다.
근데 종이 갯수를 저장하는 배열을 전역변수로 선언하여 재귀함수에서 접근할 수 있도록 하면 편하겠다는 생각이 들었다!
흰색종이는 0, 파란색 종이는 1이니
arr[0] → 흰색 종이 갯수
arr[1] → 파란색 종이 갯수
🙂 이거지
🚢 Keep going
배열을 검사하고, 하나의 종이로 이루어져 있지 않으면 재귀함수 4개를 호출한다.
검사를 어떻게 할지 고민하다가 이전값하고 다르면 하나의 종이로 이루어져 있지 않다고 생각하기로 했다!
void recur(vector<vector<int>> &v,int horizonIndex, int verticalIndex, int squareSize){
if(squareSize == 1){
//인덱스의 종이 숫자++
white_blue[v[verticalIndex][horizonIndex]] ++;
}
// 종이 검사하기
int beforeValue = v[verticalIndex][horizonIndex];
for(int i=0;i<squareSize;i++){
for(int j=0;j<squareSize;j++){
if(beforeValue == v[verticalIndex+i][horizonIndex+j]) {
if(i==squareSize-1 && j==squareSize-1){
cout<<"검사 통과!"<<endl;
white_blue[beforeValue]++;
}
beforeValue = v[verticalIndex+i][horizonIndex+j];
}
else{
recur(v,horizonIndex,verticalIndex,squareSize/2);
recur(v,horizonIndex+(squareSize/2),verticalIndex,squareSize/2);
recur(v,horizonIndex,verticalIndex+(squareSize/2),squareSize/2);
recur(v,horizonIndex+(squareSize/2),verticalIndex+(squareSize/2),squareSize/2);
break;
}
}
}
}이 함수를 호출해주자.
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin>>t;
vector<vector<int>> v(t,vector<int>(t,0));
for(int i=0;i<t;i++) {
for (int j = 0; j < t; j++) {
cin >> v[i][j];
}
}
for(int i=0;i<t;i++) {
for (int j = 0; j < t; j++) {
cout<<v[i][j]<<" ";
}
cout<<"\n";
}
recur(v,0,0,t);
cout<<"white : "<<white_blue[0]<<"\n";
cout<<"blue : "<<white_blue[1]<<"\n";
return 0;
}우오아아아...한번에 에러없이 예제가 풀렸다!
제출하기 전에 Check할 것!
- 입력, 계산, 출력값이 int의 자료를 넘어가는가? (int = 2,147,483,648)
- 작은 값의 입력을 잘 해결하는가? (1, 2 정도의 입력을 해보자)
- 불필요한 log들 전부 지우고 제출해봅시당.
🙆 제출하러 갑시다 🤘
제출해도 정답이였다 :)
조아요~ ☺️
😀 FULL CODE 🤨
#include <iostream>
#include <vector>
using namespace std;
int white_blue[2] = {0,0};
void recur(vector<vector<int>> &v,int horizonIndex, int verticalIndex, int squareSize){
if(squareSize == 1){
//인덱스의 종이 숫자++
white_blue[v[verticalIndex][horizonIndex]] ++;
return;
}
// 종이 검사하기
int beforeValue = v[verticalIndex][horizonIndex];
for(int i=0;i<squareSize;i++){
for(int j=0;j<squareSize;j++){
// 이전값과 같으면??
if(beforeValue == v[verticalIndex+i][horizonIndex+j]) {
if(i==squareSize-1 && j==squareSize-1){
//검색이 끝나면 종이 ++
white_blue[beforeValue]++;
}
//이전값 갱신!
beforeValue = v[verticalIndex+i][horizonIndex+j];
}
else{
//재귀는 1사분면, 2사분면, 3사분면, 4사분면 4개!
recur(v,horizonIndex,verticalIndex,squareSize/2);
recur(v,horizonIndex+(squareSize/2),verticalIndex,squareSize/2);
recur(v,horizonIndex,verticalIndex+(squareSize/2),squareSize/2);
recur(v,horizonIndex+(squareSize/2),verticalIndex+(squareSize/2),squareSize/2);
return;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin>>t;
vector<vector<int>> v(t,vector<int>(t,0));
for(int i=0;i<t;i++) {
for (int j = 0; j < t; j++) {
cin >> v[i][j];
}
}
recur(v,0,0,t);
cout<<white_blue[0]<<"\n"<<white_blue[1];
return 0;
}🤜 FeedBack 🤛
- 솔직히 지금까지 재귀함수는 별로 좋지 않다고 생각하고 있었는데 재귀함수는 강력한 것 같다.
큰 범위 → 작은 범위로 쪼개지는 문제는 재귀를 통해서 해결할 수 있겠다! - 코드가 못생겼다. 다른 사람들이 잘 알아볼 수는 있을까?
이쁜 코드를 찾아보고 이쁜 코드를 작성하는 방법을 정리해야겠다.
Raeyoung's feedback
- 이전 값과 계속 비교할 필요가 없다! 그냥 첫번째 값과 계속 비교하면 됨
→ 이전값 갱신이 불필요한 코드라는 것. - vertical.... horizon.... 괜히 코드만 길어지는 것. → 편하게 matrix[y][x]로 가자.
- const nl = "\n";
cout << nl;
