https://programmers.co.kr/learn/courses/30/lessons/68936
코딩테스트 연습 - 쿼드압축 후 개수 세기
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15]
programmers.co.kr
[난이도] level2
[유형] 분할정복
[풀이]
정사각형의 수가 모두 같지 않다면 4개로 분할된 정사각형을 다시 검사하도록
재귀함수를 호출해주고 모두 같다면 0,1인지에 따라 개수를 1개 더해줍니다.
#include <string> #include <vector> using namespace std; vector<int> answer(2); vector<vector<int>> arr; int same(int y,int x,int n){ int t = arr[y][x]; for(int i=y;i<y+n;i++) for(int j=x;j<x+n;j++) if(t!=arr[i][j]) return -1; return t; } void sol(int y,int x,int n){ int ret = same(y,x,n); if(ret!=-1){ answer[ret]++; return; } int b = n/2; sol(y,x,b); sol(y+b,x,b); sol(y,x+b,b); sol(y+b,x+b,b); } vector<int> solution(vector<vector<int>> _arr) { arr=_arr; sol(0,0,arr.size()); return answer; }
https://github.com/has2/Problem-Solving/blob/master/programmers/level2/쿼드압축 후 개수 세기.cpp
'Problem-Solving > Programmers' 카테고리의 다른 글
[Codeforces][Round #736][Div.2] A : Gregor and Cryptography (0) | 2021.08.06 |
---|---|
[프로그래머스][level2] 숫자의 표현 (C++) (0) | 2021.08.06 |
[프로그래머스][level2] 이진 변환 반복하기 (C++) (0) | 2021.08.06 |
[프로그래머스][level2] 2개 이하로 다른 비트 (C++) (0) | 2021.08.06 |
[프로그래머스][level2] 삼각 달팽이 (C++) (0) | 2021.08.06 |