[백준] No.1780 - 종이의 개수 (C++)

문제

www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

풀이

간단한 분할 정복 문제. 대체로 분할 정복 문제들은 입력이 굉장히 큰 경우가 많아 브루트 포스로 접근하면 시간 초과가 발생한다. 해당 문제도 최대 3^7의 큰 입력을 받는다.

 

행렬은 항상 같은 크기인 9개의 종이로 자르기며 재귀호출을 하기 아래와 같은 기저 사례가 필요하다.

기저 사례: 잘라진 크기가 1인 경우 해당 origin_paper[row][col] 값을 바로 반환한다.

 

 

위의 기저 사례를 갖는 재귀 함수 int CountPaperValue(int size,int row,int col) 를 구현한다.

 

크기가 1보다 크다면 paper_value[9]에 각 9가지의 위치로부터 CountPaperValue()를

재귀 호출해준다.

 

만약 9가지의 값들이 다르다면 해당 종이의 count값들을 +1 해준다.

9가지가 모두 같다면 해당 값을 바로 반환한다.

 

최종적으로 모든 칸이 같은 경우를 대비해 result 값을 확인하여 예외처리를 해준다.

 

 

코드

	#include <iostream>
	#include<vector>
	#include<string>
	using namespace std;
	int paper_size;
	int paper_count[3]; // -1 => [0], 0=>[1] , 1=>[2]에 저장
	vector<vector<int>> origin_paper;
	int CountPaperValue(int size,int row,int col){
	if(size == 1)
	return origin_paper[row][col];
	bool is_all_same= true;
	int paper_value[9];
	int divided_size = size/3;
	int cnt=0;
	for(int i=0 ; i<3 ; i++)
	for(int j=0 ; j<3 ; j++)
	paper_value[cnt++] =CountPaperValue(divided_size, row + (divided_size*i), col+ (divided_size*j));
	for(int i=0; i<8 ; ++i)
	if(paper_value[i] != paper_value[i+1]){
	is_all_same =false;
	break;
	}
	if(!is_all_same){ // 9개가 같지 않는 경우 2를 반환
	for(int i=0; i<9 ; ++i)
	++paper_count[paper_value[i]+1];
	return 2;
	}else
	return paper_value[0];
	}
	int main() {
	int temp_num;
	cin>>paper_size;
	for(int i=0; i<paper_size ; ++i){
	vector<int> temp_vec;
	for(int j=0; j<paper_size ; ++j){
	cin>>temp_num;
	temp_vec.push_back(temp_num);
	}
	origin_paper.push_back(temp_vec);
	}
	int result =CountPaperValue(paper_size, 0, 0);
	if(result !=2)
	++paper_count[result+1];
	for(int i=0; i<3 ; ++i)
	cout<<paper_count[i]<<'\n';
	return 0;
	}

view raw 종이의 개수.cpp hosted with ❤ by GitHub