[백준] 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 값을 확인하여 예외처리를 해준다.

 

 

코드