대엉코딩

www.acmicpc.net/problem/15659

1. 풀이방법

- 일단 숫자는 고정이고, 연산자만으로 모든 순열을 다 짜고 연산을 시작한다.

- 문제는 연산자 우선순위에 따른 계산을 해야한다는 것인데

- 저 같은경우 * 또는 / 먼저 연산을 완료한 후 새로운 벡터에 넣어놓고 그 후 + 또는 - 연산을 해주었습니다.

- 이과정에서 구현이 매우 까다로웠는데,

- 먼저 해야하는 것은 * 또는 / 가 나오는 경우 이 연산자들이 연속되어있는 곳 까지는 연산을 계속해줍니다.

(예를 들어 5+7*4*3-3) 이런 경우 *가 처음 등장하면 뒤쪽에 -가 나오기 전까지는 쭉 연결해서 연산을 해줍니다.

- 그후 덧셈, 뺄셈 연산을 수행하는데, 예외사항들이 많아 너무 복잡한 문제였습니다. 개인적으로......

- 저 말고는 제 코드를 이해하는 분이 계실지가..ㅋㅋㅋㅋ

2. 주의사항

- 테스트케이스를 보면서 수정해나가면서 짠 후 ,, 90퍼에서 계속 실패가 떠서 예외사항을 직접 찾아 해매야 했습니다.

3. 나의코드

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int N,tmp;
vector<long long> numarr;
vector<long long> oper;
vector<long long> tmpoper;
long long maxresult = -9999999999;
long long minresult = 9999999999;
bool allplusorminus;

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) { cin >> tmp; numarr.push_back(tmp); }
	for (int i = 0; i < 4; i++) { cin >> tmp; oper.push_back(tmp); }
}

int makenum() {
	vector<long long> tmparr;
	int index = 0;
	for (int i = 0; i < tmpoper.size(); i++) { //곱셈 나눗셈 먼저
		if (tmpoper[i] == 2 || tmpoper[i] == 3) {
			int tempint=numarr[index];
			while (1) { //연속되는 곱셈,나눗셈까지는 모두 같이 처리
				if (i == tmpoper.size() || tmpoper[i] == 0 || tmpoper[i] == 1) { index++; break; }
				if (tmpoper[i] == 2) { //곱셈
					tempint *= numarr[index + 1];
					index++;
				}
				else { //나눗셈
					tempint /= numarr[index + 1];
					index++;
				}
				i++;
			}
			tmparr.push_back(tempint);
			i--;
		}
		else { //아래와 같이 생각해줘야할 예외사항이 너무 많다.!!!!!!!!!!!!!!!
			if (i==0 || i == tmpoper.size() - 1){ 
				tmparr.push_back(numarr[index]); index++;
				if (tmpoper.size() == 1) tmparr.push_back(numarr[index]);
			}
			if (i < tmpoper.size() - 1 && (tmpoper[i + 1] == 0 || tmpoper[i + 1] == 1)) { 
				tmparr.push_back(numarr[index]);
				index++;
			}
		}
	}
	long long result=tmparr[0];
	index = 1;
	for (int i = 0; i < tmpoper.size(); i++) {
		if (tmpoper[i] == 0 || tmpoper[i] == 1) {
			if (tmpoper[i] == 0) { // 덧셈
				result += tmparr[index];
				index++;
			}
			else { //뺄셈
				result -= tmparr[index];
				index++;
			}
		}
	}
	return result;
}

void makecase(int cnt) {
	if (cnt == N - 1) {
		/*cout << numarr[0];
		for (int i = 0; i < tmpoper.size(); i++) {
			if (tmpoper[i] == 0) { cout << " + "; }
			if (tmpoper[i] == 1) { cout << " - "; }
			if (tmpoper[i] == 2) { cout << " * "; }
			if (tmpoper[i] == 3) { cout << " / "; }
			cout << numarr[i + 1];
		}
		cout << "\n";*/
		if (makenum() > maxresult) { maxresult = makenum(); }
		if (makenum() < minresult) { minresult = makenum(); }
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (oper[i] != 0) {
			tmpoper.push_back(i);
			oper[i]--;
			makecase(cnt + 1);
			oper[i]++;
			tmpoper.pop_back();
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	makecase(0);
	cout << maxresult << "\n" << minresult << "\n";
	return 0;
}

www.acmicpc.net/problem/2422

1. 풀이방법 

- 1~N까지의 모든 아이스크림 중 3개를 만드는 모든 조합을 골라서

- 이게 가능한지 (최악의 조합에 속하는 것이 없는 지) 를 확인 후 방법의 수를 증가시켜 주면되는 문제였습니다.

- 조합을 만드는 것은 어렵지 않았고, 처음에는 최악의 조합을 <pair<int,int>>로 만들어

- 반복문을 통해서 psice() 가능한 아이스크림조합인지를 확인 했었는데, 시간초과가 발생하였습니다.

- 반복문 탐색 중 정지 조건 break 를 걸어 주고 난 뒤 제출해도 역시 시간초과 였습니다.

- 그래서 이차원배열을 선언하여 두 아이스크림이 최악의 조합인지를 O(1) 시간에 확인할 수 있도록

- 수정하여 제출 하였더니 통과 되었습니다.

- 그래프 구현방법 중 인접행렬 방식( 두 노드가 인접했는지 확인하는 것이 매우 빠르다라는 장점)

- 으로 부터 나온 생각으로 구현하였습니다.

2. 주의사항

- 문제 자체는 쉬웠지만, 시간을 단축하는 부분에 있어 특이점이 있는 것 같아 포스팅으로 남깁니다.

3. 나의코드 

- 주석 부분은 반복문을 통한 탐색 부 입니다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

int N;
int M;
int t1, t2;
// vector<pair<int, int>> worstice;
bool wi[201][201];
vector<int> icearr;
int pscase = 0;

/*bool psice() {
	for (int i = 0; i < worstice.size(); i++) {
		int tmp = 0;
		for (int j = 0; j < icearr.size(); j++) {
			if (icearr[j] == worstice[i].first || icearr[j] == worstice[i].second) {
				tmp++;
			}
			if (tmp == 2) return false;
			if (icearr[j] > worstice[i].second) break;
		}
	}
	return true;
}*/
bool ps() {
	if (wi[icearr[0]][icearr[1]] == true || wi[icearr[0]][icearr[2]] == true
		|| wi[icearr[1]][icearr[2]] == true) return false;
	else return true;
}

void makeice(int index,int cnt) {
	if (cnt == 3) {
		if (ps()) {
			pscase++;
		}
		return;
	}
	for (int i = index; i <= N; i++) {
		icearr.push_back(i);
		makeice(i+1,cnt + 1);
		icearr.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0); cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> t1 >> t2;
		// worstcase.push_back({t1,t2});
		wi[t1][t2] = true;
		wi[t2][t1] = true;
	}
	makeice(1,0);

	cout << pscase << "\n";

	return 0;
}

www.acmicpc.net/problem/18511

1. 풀이방법

- 처음 문제를 보고 눈에 띈 숫자는 N이 최대 100,000,000 이므로 선형적으로 증가시켜가며 N과 비교하면 시간초과

- 그러면 주어진 집합을 보고 숫자를 구성해서 N과 비교를 해야 겠다.

- 그래서 자릿수 계산하고 앞자리 수 부터 비교를 해 가면서 어떤 원소를 자릿수에 넣고 해야겠다~~ 라면서 하다보니

- 되게 다양한 경우의 수가 있고 생각보다 너무 복잡하였습니다.....하

- 그래서 문제를 다시 읽어보니..... 매우 쉬워지는 이유가 하나 있었습니다 K의 원소의 개수가 최대 3개 라는 것....!

- 저는 K의 집합 원소가 1~9 이고 집합의 원소의 수 도 역시 최대 10개라고 당연시? 생각해서...

- 이 모두를 조합하는 수는 너무 많다 라고 생각했었는데 아니였습니다...

- 최대 3개 이므로 그냥 모든 조합을 만들어 내서 N가 비교하고 N보다 작거나 같을경우의 수를 모두 벡터에 넣고

- 그 중 최대값을 출력하였습니다.

2. 주의사항

- 문제를 똑바로 파악하고 시작할 것 !!!!

3. 나의코드

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int n, k,tmp;
vector<int> numarr;
vector<int> resultarr; //n을 쪼개놓자

bool compare(int& lhs, int& rhs) {
	if (lhs > rhs) return true;
	else return false;
}

void makecase(int num,int cnt) {
	if (cnt!=0 && num <= n) { 
		resultarr.emplace_back(num);
	}
	if (num > n) return;
	for (int i = 0; i < k; i++) {
		if (cnt == 0) { makecase(num * numarr[i],cnt+1); }
		else makecase(num*10+numarr[i],cnt+1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> k;
	
	for (int i = 0; i < k; i++) {
		cin >> tmp;
		numarr.emplace_back(tmp);
	}
	sort(numarr.begin(), numarr.end(), compare);
	makecase(1,0);
	sort(resultarr.begin(), resultarr.end(), compare);
	cout << resultarr[0];
	return 0;
}

www.acmicpc.net/problem/9663

1. 풀이방법

- N개의 퀸을 놓을 수 있는 경우의 수 를 구하는 문제이고, 모든 경우의 수를 탐색하는데 시간을 신경써야합니다.

- 처음에는 그냥 dx[8],dy[8] 을 선언해서 8방향을 모두 탐색하다가 이미 다른 퀸이 있으면 리턴하고 라는 식으로

- 구현을 했다가.....N=5일때 까지 였나...? 까지 밖에 나오지 않았습니다...

- 처음에 N이 최대 14이길래 시간초과는 신경 안써도 되는 줄 알고 짰다가 당황한 문제였습니다.

- 체스판의 특성을 이용하여 x,y좌표의 특징들을 이용해서 놓을 수 있는지를 판단해야 했습니다.

2. 주의사항

- 체스판의 특성을 활용, 시간초과를 주의해야 함.

- 2차원 배열이 아닌 1차원배열을 이용하여 [x]=y를 통해 x,y 좌표를 나타내는 것이 처음에는 생소할 수 있음

3. 나의코드

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int N;
int resultcount = 0;
int queenarr[15]; //[x]= y
 // 0~ N-1까지 사용
bool checking(int x, int y) {
	for (int i = 0; i < x; i++) {
		if ( abs(y-queenarr[i]) == abs(x -i) || queenarr[i] == y) {
			return false;
		}
	}
	return true;
}
void makecase(int x) {
	if (x == N) {
		resultcount++; return;
	}
	for (int i = 0; i < N; i++) {
		if (checking(x, i)) {
			queenarr[x] = i;
			makecase(x + 1);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	makecase(0);
	cout << resultcount << "\n";
	return 0;
}

www.acmicpc.net/problem/1107

1. 풀이방법

- 개인적으로 참 어려웠던 문제였습니다...

- 처음에는 경우의 수를 나눠서 1번 (+,-만으로만 접근) 2번 (버튼만으로 접근이 가능한 경우) 3번 (버튼으로 근접하게 간 후 +,- 로 이동해야하는 경우) 3가지 중 min 값을 출력하자 라고 했습니다.

- 하지만 저 3번....! 저걸 찾아내는게 굉장히 까다로웠습니다. 숫자를 하나씩 맞춰본다거나, 

  고장난 버튼이면 최대한 근접한 버튼을 누르는데 위,아래 어느 숫자쪽으로 탐색을 해야하나....

- 하나의 아이디어를 준 것은 바로 +,-는 마지막에 눌러진다는 것입니다. +,- 버튼을 누르고 나서 숫자를 누를경우 

  처음 부터 다시 숫자를 매겨야 하죠 (보통의 리모컨을 생각해 보시면 될 것 같습니다.)

- 그래서 생각해낸 것은 바로.....!

- 1. 일단 -1로 모든번호를 저장할 테이블들을 모두 초기화 ! (위로 갔다가 -로 돌아오는 경우도 있으므로 백만까지)

- 2. 버튼으로 이동할 수 있는 번호의 경우 테이블에 미리 다 몇번의 버튼을 눌러서 갈 수 있는지 저장!!!!

- 3. 찾고자 하는 채널이 -1, 즉 버튼만으로 갈 수 없는 경우 위,아래로 탐색해서 가장 가까이 있는 버튼으로 갈 수 있는

      번호를 찾는다 !!!!!!

( 물론 상기의 과정 중 +,- 버튼만으로 가는 것이 더 적은 수로 이동할 수 있는 경우 그 숫자를 넣어줘야 합니다.)

2. 주의사항

- 리모콘은 고장나면 쫌 사자.....

3. 나의코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

int N,M;
int remote[10]; //0~9
int casestore[1000001];
int len;

bool onlynum(int num) {
	len = 0;
	int tmp = num;
	while (1) {
		if (remote[tmp % 10] == true) return false; //고장나서 버튼만으로는 이동불가
		tmp /= 10;
		len++;
		if (tmp == 0) break;
	}
	return true;
}
void inputs() {
	cin >> N >> M;
	int tmp;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		remote[tmp] = true; //true는 고장
	}
}
void makecase() {
	casestore[100] = 0;
	for (int i = 0; i < 1000001; i++) {
		if (i == 100) continue;
		if(onlynum(i)==true)
		{
			casestore[i] = min(abs(i - 100), len);
		}
	}
}
void setcase() {
	for (int i = 0; i < 1000001; i++) {
		casestore[i] = -1;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	setcase();
	makecase();

	if (N == 100) { cout << 0 << "\n"; return 0; }
	if(casestore[N]!=-1){
		cout << casestore[N] << "\n"; return 0;
	}
	else{
		int index = 1;
		while (1) {
			if (N - index >= 0) {
				if (casestore[N - index] != -1) {
					cout << min(abs(N - 100),casestore[N - index] + index) << "\n";
					return 0;
				}
			}
			if (N + index <= 1000000) {
				if (casestore[N + index] != -1) {
					cout << min(abs(N - 100),casestore[N + index] + index) << "\n";
					return 0;
				}
			}
			index++;
		}
	}
	return 0;
}

www.acmicpc.net/problem/14500

1. 문제풀이 방법

- 테트리스에 너무 익숙한 탓일까요....?

- 문제조건에서 대칭을 시켜도 된다는 조건을 빼먹고...이건 뭐 아이디어가 안떠올라서 모든 좌표탐색을 했으나

- 대칭을 안넣었으니...당연히 틀릴 수 밖에 없었습니다....

- 문제 조건을 다시 파악하고 보니 DFS 깊이 4짜리에 해당하는 모든 좌표가 테트로미노로 표현이 된다는 것을

  알아내었습니다....

- 하지만 ㅗ ㅏ ㅜ ㅓ 는 DFS로 표현이 불가능 합니다 (집합느낌으로 보면 테트로미노 > 4짜리 DFS?) 이런느낌?

- 그래서 그건 따로 직접 좌표를 설정해 구해주었습니다.

2. 주의사항

- 문제를 똑바로 파악하자!!!!

3. 나의코드

#include<iostream>
#include<algorithm>
using namespace std;

int N, M;
int tetro[501][501];
int maxvalue = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool visit[501][501];
int depth = 0;
int tmpsum;

void dfs(int x, int y) {
	if (depth == 4) {
		if (tmpsum > maxvalue) maxvalue = tmpsum;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int x2 = x + dx[i];
		int y2 = y + dy[i];
		if (x2 >= 0 && x2 < N &&y2 >= 0 && y2 < M && visit[x2][y2]==false) {
			visit[x2][y2] = true;
			depth++;
			tmpsum += tetro[x2][y2];
			dfs(x2, y2);
			tmpsum -= tetro[x2][y2];
			depth--;
			visit[x2][y2] = false;
		}
	}
}

void cantdfs(int x, int y)
{
	int result = 0;
	if (x - 1 >= 0 && y + 2 < M) {// ㅗ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x][y + 2] + tetro[x - 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 1 < N &&y + 2 < M) { // ㅜ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x][y + 2] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 1 < N &&x - 1 >= 0 && y + 1 < M) { // ㅓ
		result = tetro[x][y] + tetro[x][y + 1] + tetro[x - 1][y + 1] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
	if (x + 2 < N &&y + 1 < M) {
		result = tetro[x][y] + tetro[x + 1][y] + tetro[x + 2][y] + tetro[x + 1][y + 1];
		if (result > maxvalue) maxvalue = result;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tetro[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			depth = 1;
			tmpsum = tetro[i][j];
			visit[i][j] = true;
			dfs(i, j);
			visit[i][j] = false;
			cantdfs(i, j);
		}
	}
	cout << maxvalue << "\n";

	return 0;
}

www.acmicpc.net/problem/17135

1.풀이방법

- 3명의 궁수가 (N,0) (N,M-1)까지 배치될 수 있는 모든 CASE를 생성하여 게임을 시작합니다. (조합)

- 격자에서 모든 적이 사라지면 게임을 종료

- 3명의 궁수를 대상으로 모든 적들의 거리를  계산후 좌표와 거리를 구조체로 선언하여, eset(enemy set)에 넣고

- sort를 진행(거리가 가까운 순, 같으면 좌표 y가 더 작은 순(왼쪽))

2. 주의사항

- 조합만 잘 구현하면 문제는 조건대로 찬찬히 구현하면 해결 완료.

3.나의코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int ground[17][17];
int copyground[17][17];
bool selected[17];
vector<pair<int, int>> archer;
int maxresult = -1;
int N, M;
int D;
int enemycount;
struct enemy { int x; int y; int d; };

bool cmp(enemy a, enemy b) {
	if (a.d < b.d) { return true; }
	else {
		if (a.d == b.d) {
			if (a.y < b.y) { return true; }
			else { return false; }
		}
		return false;
	}
}

void inputs() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> ground[i][j];
			copyground[i][j] = ground[i][j];
		}
	}
}
void groundinit() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			ground[i][j] = copyground[i][j];
		}
	}
}
bool checkground() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (ground[i][j] == 1) { return false; }
		}
	}
	return true;
}
int abs(int n1, int n2) {
	if (n1 > n2) { return n1 - n2; }
	else return n2 - n1;
}
int getdistance(int x, int y, int x2, int y2) {
	return (abs(x, x2) + abs(y, y2));
};
void enemymove() {
	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j < M; j++) {
			if (ground[i][j] == 1) {
				ground[i + 1][j] = 1; ground[i][j] = 0;
			}
		}
	}
}
void startgame() {
	while (1) {// 반복한번 = 1턴
		if (checkground() == true) { 
			if (maxresult < enemycount) { maxresult = enemycount; }
			return;
		}
		vector<enemy> eset[3];
		for (int i = 0; i < archer.size(); i++) {
			for (int a = 0; a < N; a++) {
				for (int b = 0; b < M; b++) {
					if (ground[a][b] == 1) {
						if (getdistance(archer[i].first, archer[i].second, a, b) <= D) {
							enemy tmp; tmp.x = a; tmp.y = b; tmp.d = getdistance(archer[i].first, archer[i].second, a, b);
							eset[i].push_back(tmp); //1명의 궁수당 적이 들어있음 거리와 함께
						}
					}
				}
			}
			sort(eset[i].begin(), eset[i].end(), cmp);
		}
		//각각의 궁수에 대해서 0번쨰 인덱스의 적이 죽을 차례
		for (int i = 0; i < archer.size(); i++) {
			if (eset[i].empty() == true) continue; //사정거리내의 적이 없음
			if (ground[eset[i][0].x][eset[i][0].y] == 1) {
				ground[eset[i][0].x][eset[i][0].y] = 0; //적을 없앤다
				enemycount++;
			}
		}
		enemymove();
	}
}


void makecase(int index,int num) {
	if (num == 3) {
		enemycount = 0;
		groundinit();
		startgame(); return;
	}
	pair<int, int> tmp;
	tmp.first = N;
	for (int i = index; i < M; i++) {
		if (selected[i] == true  ) continue;
		tmp.second = i;
		archer.push_back(tmp);
		selected[i] = true;
		makecase(i,num + 1);
		archer.pop_back();
		selected[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	inputs();
	makecase(0,0);
	cout << maxresult;

	return 0;
}

www.acmicpc.net/problem/17136

1. 풀이방법

- 하... 이문제 때문에 여간 고생한게 아니다;;

- 정확한 이유는 모르겠는데 처음에 맵을 탐색하다가 1을 발견하면 5가지의 색종이를 모두 붙이는 식으로

- 구현을 했었는데 계속 종료조건이 애매해서 어쩔 줄 몰라 하다가,,,, 탐색을 하는 부분이랑 색종이를 붙여보는

- 것을 나눠서 구현했더니 해결이 되었습니다.

- 자신감이 딱 붙어갈 타이밍에 좌절을 준 문제였습니다.....나중에 다시 풀어도 고생할 듯한....

- 전체적인 구조를 종료조건을 잘 생각해서 짜야할 것 같습니다.... 아이디어는 금방 떠올렸으나..참;;

- 개인적으로 힘든 문제였습니다..

2.주의사항

- 종료조건을 적절히 사용할 수 있게끔 전체적인 구조를 생각하고 짜자.....!

3.나의 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int map[10][10];
int colorpaperset[6];
int minimumpapaer = 101;
void doattach(int, int, int);

void inputsetting() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 1; i < 6; i++) {
		colorpaperset[i] = 5;
	}
}
bool canattach(int x, int y, int r) {
	if (x + r > 10 || y + r > 10) { return false; }
	for (int i = x; i < x+r; i++) {
		for (int j = y; j < y+r; j++) {
			if (map[i][j] == 0) return false;
		}
	}
	return true;
}
void setmap(int x, int y, int r) {
	for (int i = x; i < x + r; i++) {
		for (int j = y; j < y + r; j++) {
			map[i][j] =0;
		}
	}
}
void unsetmap(int x, int y, int r) {
	for (int i = x; i < x + r; i++) {
		for (int j = y; j < y + r; j++) {
			map[i][j] = 1;
		}
	}
}

void attach(int x, int y, int r) {
	int tmpx, tmpy;
	bool c = false;
	for (int i = x; i < 10; i++) { //1인 부분을 탐색
		for (int j = 0; j < 10; j++) {
			if (map[i][j] == 0) {
				if (i == 9 && j == 9) { minimumpapaer = min(minimumpapaer, r); return; }
				// 재귀를 통해 여기까지 왔다는 것 자체가 이미 1을 다 0으로 바꾸고 도착했다는 것
				continue;}
			tmpx = i; tmpy = j; c = true; break;
		}
		if (c == true) break;
	}
	doattach(tmpx, tmpy, r);
}
void doattach(int x, int y, int r) {//붙이기를 시도한다.
	for (int k = 5; k > 0; k--) {
		if (canattach(x, y, k) == true && colorpaperset[k] > 0) {
			setmap(x, y, k);
			colorpaperset[k]--;
			attach(x, y, r + 1); //재귀를 통해 다시 탐색을 수행
			colorpaperset[k]++; //다른 종이에 대해서도 수행을 해봐야하므로
			unsetmap(x, y, k); //원상 복구
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputsetting();
	attach(0, 0, 0);
	if (minimumpapaer == 101) { cout << -1; }
	else { cout << minimumpapaer; }
	return 0;
}