알고리즘 공부/백준
[백준] No.1780 - 종이의 개수 (C++)
EVEerNew
2020. 10. 30. 22:52
반응형
문제
1780번: 종이의 개수
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.
www.acmicpc.net
풀이
간단한 분할 정복 문제. 대체로 분할 정복 문제들은 입력이 굉장히 큰 경우가 많아 브루트 포스로 접근하면 시간 초과가 발생한다. 해당 문제도 최대 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 값을 확인하여 예외처리를 해준다.
코드
반응형