종이의 개수

#include <iostream>
using namespace std;
//9개로 계속 나눈다
int N; int mone,zero,one;
int arr[2187][2187];
void addNum(int x,int y){
      if(arr[x][y]==-1) mone++;
      else if(arr[x][y]==0) zero++;
      else if(arr[x][y]==1)one++;
      return; 
}
bool isSame(int x,int y,int size){
   for(int i=x;i<x+size;i++){
      for(int j=y;j<y+size;j++){
         if(arr[x][y]!=arr[i][j]) return false;
      }
   }
   return true;
}
void sol(int x,int y, int size){
   if(size==1||isSame(x,y,size)) {
      addNum(x,y);
      return; 
   }
   for(int i=x;i<x+size;i+=size/3){
      for(int j=y;j<y+size;j+=size/3){
         sol(i,j,size/3);   
      }
   }
}
int main() {
   cin>>N;
   for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
         cin>>arr[i][j];
   sol(0,0,N);
   cout<<mone<<'\n'<<zero<<'\n'<<one;
   return 0;
}
//15686 prev_permutaion
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int,int>> home;
vector<pair<int,int>> dak;

vector<int> v;
int map[51][51];
int N,M;
int ans=1000000000;
int main() {
	cin>>N>>M;
	int n=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
		int x=0;
		cin>>x;
		if(x==1) home.push_back({i,j});
		if(x==2) {n++;dak.push_back({i,j});}
		}
 	}
 //	cout<<n<<'\n';
 	for(int i=0;i<n;i++){
 		if(i<M) v.push_back(1);
 		else v.push_back(0);
 	}
 
	do{	
		int dist[110]={0};
		int sum=0;
		for(int i=0;i<dak.size();i++){
			if(v[i]!=1) continue;
			int x=dak[i].first;
			int y=dak[i].second;
			int j=0;
				for(auto [u,v]:home){
					int temp=abs(u-x)+abs(y-v);
					if(!dist[j]) dist[j]=temp;
					else if(dist[j]>temp) dist[j]=temp;
					j++;
				}
		}
		for(int i=0;i<home.size();i++){
		sum+=dist[i];
		}
		ans=min(ans,sum);
	}while(prev_permutation(v.begin(),v.end()));

	cout<<ans;
	return 0;
}
//외판원 순회 비트마스킹
#include <iostream>
#include <cstring>
using namespace std;
int N;
int W[17][17];
int dp[17][1<<17];      // 0,1,2,3 -> 모두 방문 시 1<<4-1

int sol(int i,int visited){
	if(visited==(1<<N)-1) { //모두 방문
		if(W[i][0]>0) return W[i][0];
		else return 1000000000;
	}
	int &ret=dp[i][visited];
	if(ret!=-1) return ret;
	ret= 1000000000;
	for(int j=0;j<N;j++){
		int k=visited & (1<<j); //방문했냐
		if(k>0 || W[i][j]==0) continue;
		ret=min(ret,sol(j,visited |(1<<j))+W[i][j]);
	}
	return ret;
}
int main() {
	cin>>N;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cin>>W[i][j];
		}
	}
	memset(dp,-1,sizeof(dp));
	cout<<sol(0,1);
	return 0;
}