대엉코딩

www.acmicpc.net/problem/1715

1. 풀이방법

- 작은 순서대로 정렬하여 카드 묶음을 묶어나가면 된다.

- 주의할 점은 처음에만 정렬하고 앞쪽부터 연산 한다고 해결되는 것이 아니다

- 만약에 20 30 40 45 70 이 있을 떄 20+30=50이 되고 연산 순서를 그대로 하면 50 40 45 70 이 된다.

- 이러면 50+40이 먼저 계산 되므로 분명 오답을 가지고 올 것이다.

- 그럼으로 한번의 연산을 할 때마다 계산을 앞으로 해야할 배열들은 정렬되어 있어야 한다.

2. 주의사항

- 위의 로직을 처음에 그대로 vector와 sort로 구현하였다...물론 답은 맞겠지만 입력사이즈를 고려하면 시간초과가 뜬다.

  (매 단계마다 sort를 할 경우)

- 그래서 priority_queue 우선순위 큐를 이용하였다 <오름차순으로> 그러면 단계마다 합친 결과를 push 할 때 정렬 되

- 어 큐에 들어가므로 sort를 할 필요가 없다.

- 한번에 두개를 큐에서 꺼내고 그 합을 다시 넣어주므로 반복문은 N번이 아닌 N-1번만 돈다.

3. 나의코드

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

int N;
priority_queue<int, vector<int>, greater<int>> carddeck;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int card;
	for (int i = 0; i < N; i++) {
		cin >> card; carddeck.push(card);
	}
	int minsum = 0;
	int tmpcard1, tmpcard2;
	for (int i = 0; i < N-1; i++) {
		tmpcard1=carddeck.top();
		carddeck.pop();
		tmpcard2 = carddeck.top();
		carddeck.pop();
		minsum += (tmpcard1 + tmpcard2);
		tmpcard2 += tmpcard1;
		carddeck.push(tmpcard2);
	}
	cout << minsum;
	return 0;
}

www.acmicpc.net/problem/10825

1. 풀이방법

- algorithm 라이브러리 내에 정의되어있는 sort를 사용하였습니다.

- 이를 사용한다는 가정하에 cmp함수를 원하는 대로 작성할 수 있는지를 물어보는 문제인 것 같습니다.

- 조건 그대로 작성해주시면 됩니다.

- 코드의 길이를 줄일 수 있지만 저는 보통 아래의 코드의 형식을 벗어나게 작성하지는 않습니다.

- 이 문제처럼 이것만을 물어보기 위한 경우가 아닌 경우 보통 이렇게까지 분류조건이 많이 달리지는 않는데 그랬을 때

  코드 한 두줄 정도 더 길지만 저 같은 경우 의미 파악이 그게 더 분명히 되서 실수할 가능성도 줄고 해서 그대로 작성

  하는 편입니다.

2. 주의사항

- 증가순, 감소순 정확히 구별

3. 나의코드

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

int N;
struct studentscore {
	int kor; int eng; int mat;
	string name;
};
vector<studentscore> studentarr;

bool cmp(studentscore s1, studentscore s2) {
	if (s1.kor > s2.kor) { return true; }
	else if(s1.kor==s2.kor){
		if (s1.eng < s2.eng) return true;
		else if (s1.eng == s2.eng) {
			if (s1.mat > s2.mat) return true;
			else if (s1.mat == s2.mat) {
				if (s1.name< s2.name) return true;
				return false;
			}
			else return false;
		}
		else return false;
	}
	else return false;
}

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		studentscore tmps;
		cin >> tmps.name >> tmps.kor >> tmps.eng >> tmps.mat;
		studentarr.push_back(tmps);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	sort(studentarr.begin(), studentarr.end(), cmp);
	for (int i = 0; i < studentarr.size(); i++) {
		cout << studentarr[i].name << "\n";
	}
	return 0;
}

www.acmicpc.net/problem/16234

1. 풀이방법

- 조건이 조금 많긴 하지만 하나씩 처리하면 구현자체가 많이 어렵지는 않습니다..

- while문 안 쪽에서 dfs를 통해서 구역들을 연결해주며 peoplesum에 인구수의 합을 저장하고, nationcount에 구역의 수를 저장.

-그리고 나중에 인구수의합/구역의 수 로 각 연결된 구역의 값을 초기화 해주어야하는데 dfs를 이용했으므로 저는

따로 vector를 선언해서 x,y를 저장해 놓은 뒤 배정 해두었으나....지금 생각해보니 dfs 수행 부 뒤쪽에서 초기화를 해줘도 될 것으로 보이네요....! 이런......!

-백준 알고리즘 사이트에서는 이 문제의 분류를 너비우선탐색으로 기재해놓았던데, bfs로 구현할 수 있을 것 같긴 하지만 문제에서 주는 뉘앙스는 뭔가 dfs에 더 가까운 듯한 개인적인 느낌입니다.

2. 주의사항

- 조건을 꼼꼼히 살필 것.

- 방문(visited) 배열을 초기화 해주는 작업이 필요하다(인구수 이동이 일어난 이후, 다음 인구수 이동이 일어나기 전에)

3. 나의 코드

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

int N, L, R;
int ground[51][51];
int visited[51][51];//방문여부 체크
int dx[4] = { 0,0,-1,1 }; //4방향 탐색
int dy[4] = { 1,-1,0,0 };
int peoplesum = 0; //구역의 인구수 합
int nationcount = 0; // 구역의 수
int resultcount; //몇번의 인구이동
bool finish = false; //인구이동이 한번이라도 일어났는지를 체크하기 위한
vector<pair<int, int>> node; //연결된 구역들의 위치를 저장해두기 위한 벡터
pair<int, int> tmp; //임시벡터
 
void inputs() { //입력함수
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> ground[i][j];
		}
	}
}
int gapabs(int num1, int num2) { //인구수 차이를 리턴
	if (num1 > num2) return (num1 - num2);
	else return (num2 - num1);
}
void searchmove(int i,int j) { //dfs 수행부
	visited[i][j] = true;
	for (int k = 0; k < 4; k++) {
		if (i + dx[k] >= 0 && i + dx[k] < N&&j + dy[k] >= 0 && j + dy[k] < N&&visited[i+dx[k]][j+dy[k]]==false) {//방문하지 않았고, 지도 내부
			if (gapabs(ground[i][j], ground[i + dx[k]][j + dy[k]]) >= L && gapabs(ground[i][j], ground[i + dx[k]][j + dy[k]]) <= R) { //L이상 R이하인 경우만
				finish = true; //한번이라도 인구수 이동이 이동이 일어난 경우 ---> 종료조건을 위한...!!
				nationcount += 1;
				peoplesum += ground[i + dx[k]][j + dy[k]];
				tmp.first = i+dx[k]; tmp.second = j+dy[k];
				node.push_back(tmp);
				searchmove(i + dx[k], j + dy[k]); //dfs수행
			}
		}
	}
}
void initvisited() { //방문배열을 초기화 (인구이동 발생 후 초기화해주어야 함)
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visited[i][j] = false;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	while (1) { //한번의 인구이동마다 while 내부 수행
		finish = false;
		initvisited();//방문배열 초기화
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j] == false) {
					node.clear();
					nationcount = 1;
					peoplesum = ground[i][j];
					tmp.first = i; tmp.second = j;
					node.push_back(tmp); //나중에 인구수 조정을 해줘야 하므로 x,y좌표를 벡터에 넣어놓는다.
					searchmove(i, j);//dfs 수행
					if(finish==true){
						for (int i = 0; i < node.size(); i++) { //총 구역의 인구수/구역의수 를 각각 x,y,를 저장해놓았던 구역에 넣어준다.
							ground[node[i].first][node[i].second] = peoplesum / nationcount;
					}
				}
				}
			}
		}
		if (finish == false) { cout << resultcount; break; }
		else { resultcount++; }
	}
	return 0;
}

www.acmicpc.net/problem/18405

1. 풀이방법

- 전형적인 bfs문제 입니다.

- 문제만 읽어봐도 느낌이 딱 오는데, 하나의 조건이 있습니다.

- 바로 매번 번식을 하기는 하는데, 번호가 낮은 바이러스가 먼저 번식을 시작한다는 것.....!

- 그래서 처음에는 큐를 이용하여 구현을 할까 하다가

- 벡터를 이용해서 구현한 뒤, 오름차순 정렬을 하여 앞 쪽 바이러스부터 감염이 시작되도록 하였습니다.

2. 주의사항

- 번호가 낮은 바이러스 부터 번식을 시작한다는 것.

- 문제 조건 꼼꼼히 파악.

3. 나의코드

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

int N, K;
int S, X, Y;
int virusmap[201][201];
bool viruscheck[201][201];
int dx[4] = { 0,0,1,-1 }; //4방향 탐색을 위한
int dy[4] = { 1,-1,0,0 };
struct vi { int x; int y; int num; }; //바이러스 좌표와 number를 저장하는 구조체
vector<vi> tmparr; //1초마다 4방향 탐색을 진행해야하는 후보?바이러스들을 담은 set

void inputs() { //입력함수
	cin >> N >> K; 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> virusmap[i][j];
			if (virusmap[i][j] != 0) {
				viruscheck[i][j] = true;
			}
		}
	}
	cin >> S >> X >> Y;

}
bool cmp(vi a, vi b) { //바이러스 번호 순 정렬을 위한 비교함수
	if (a.num < b.num) return true;
	else return false;
}
void startinfection(int x, int y) { //4방향 탐색
	for (int i = 0; i < 4; i++) {
		if (x+dx[i]>=0&&x+dx[i]<N&&y+dy[i]>=0&&y+dy[i]<N&&viruscheck[x+dx[i]][y+dy[i]] == false) {
			virusmap[x + dx[i]][y + dy[i]] = virusmap[x][y];
			viruscheck[x + dx[i]][y + dy[i]] = true;
		}
	}
}
void makeascvirusset() { //바이러스map을 탐색해서 바이러스를 set에 넣어둔다
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (virusmap[i][j] != 0) {
				vi tmp;
				tmp.x = i; tmp.y = j; tmp.num = virusmap[i][j];
				tmparr.push_back(tmp);
			}
		}
	}
}
void searchvirus(int s, int x, int y) {
	int second = 0;
	while (1) {
		if (virusmap[x-1][y-1] != 0) { cout << virusmap[x-1][y-1]; break; } //이미 번식하고 있는 바이러스가 있으면 거기에 다른 바이러스가 올수 없으므로 바로 출력
		if (second == s) { cout << 0; break; } //시간에 맞았는데 위에 if문에 안 걸렸다는 뜻이므로 0 출력
		tmparr.clear();
		makeascvirusset();
		sort(tmparr.begin(), tmparr.end(), cmp); //set을 정렬한다(오름차순) 낮은 바이러스부터 번식을 시작하므로
		for (int i = 0; i < tmparr.size(); i++) {
			startinfection(tmparr[i].x, tmparr[i].y);
		}
		second++;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	searchvirus(S, X, Y);
	return 0;
}

www.acmicpc.net/problem/10815

1. 풀이방법

- 일단 문제 input사이즈를 보면 크다 500,000

- 만약 두번의 for문을 돌려서 탐색을 할경우 최악의경우 250,000,000,000 인데, 

- c++기준 대략 1초에 1억번의 연산을 한다고 가정하여도, 시간제한 2초를 훨씬 넘기 때문에 

- 선형탐색을 사용해서는 안된다 ----->이진탐색(binary search)를 사용하자.

- 오름차순으로 sorting을 한 후 시작한다.

2.주의사항

- 전형적인 이진탐색문제로서 이론을 그대로 코드로 옮겨주면 되겠다.

- 조건을 살짝씩 빼먹을 경우 무한루프에 자주 빠지니 조건을 꼼꼼하게 체크 해주자....>!

3. 나의코드

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

int N, M;
int Narr[500001];
int Marr[500001];

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> Marr[i];
	}
}
void bs(int start,int end,int searchnum) {
	int mid = (start + end) / 2;
	if (Narr[mid] == searchnum) { cout << 1 << " "; return; }
	if (mid >= end) { cout << 0 << " "; return; }
	if (Narr[mid] > searchnum) { bs(start, mid-1, searchnum); }
	if (Narr[mid] < searchnum) { bs(mid+1, end, searchnum); }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	sort(Narr, Narr+N);
	for (int i = 0; i < M; i++) {
		bs(0, N - 1, Marr[i]);
	}
	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/14890

1. 풀이방법.

- 말 그대로 그냥 문제 조건을 구현해야 하는데...

- 처음엔 왼쪽으로 쭉한번보고 오른쪽으로 쭉한번보고 위아래도 마찬가지로 하면된다 생각했었는데

- 223322 [L=2] 같은 경우가 안되는 것을 보고 접근 방식을 바꿨습니다.

-높이가 1차이 나는 친구를 만날경우 나보다 큰 친구면 나부터 뒤쪽을 보고

- 나보다 작은 친구면 나의 앞쪽부터 L만큼을 살펴 보았습니다.

2. 주의사항

- 나보다 큰 친구, 작은친구 의 분류로 나눠서 확인할 때, 저는 현재 위치를 INIT 앞쪽 친구를 loadmap[i][j]로 두었기 때문

- 에 비교문에서 값에 신경을 써야했습니다.

- 문제에 다양한 예시입력이 있어서 다행이었습니다.....아니였으면 꽤 오래 답을 찾아야 했을 것 같습니다.

- 후....문제에 대한 아이디어가 생각나면 그 아이디어로 해결이 될 것만 같은 [즉, 예외되는 사항이 발생하는 경우 를 잘

-떠올리지 못하는 것 같습니다]

- 코드를 작성하기 전에 한번 더 생각해보고 천천히 접근하자.....!

3. 나의코드

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

int N;
int loadmap[101][101];
int L;
int result = 0;
int init;
bool check;
bool checkrow[101];

void inputs() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> loadmap[i][j];
		}
	}
}
int gap(int a, int b) {
	if (a > b) return a - b;
	else { return b - a; }
}
void initcheck() {
	for (int i = 0; i < 101; i++) {
		checkrow[i] = 0;
	}
}
void lookr() {
	for (int i = 0; i < N; i++) {
		initcheck();
		init = loadmap[i][0];
		check = true;
		for (int j = 1; j < N; j++) {
			if (init == loadmap[i][j]) { init = loadmap[i][j]; continue; }
			if (gap(init, loadmap[i][j]) == 1) { //높이1차이
				if (init < loadmap[i][j]) { //벽을 만남(나보다 큰)
					if (j - L < 0) { check = false; break; }
					else {
						for (int k = 1; k <= L; k++) {
							if(checkrow[j-k]==true || loadmap[i][j - k] != init)
							 { check = false; break; }
						}
						for (int k = 1; k <= L; k++) {
							checkrow[j - k] = true;
						}
						if (check == false) break;
					}
				}
				else { //나보다 작은 친구를 만남
					if(j+L>N) { check = false; break; }
					else{
						for (int k = 0; k < L; k++) {
							if (checkrow[j+k]==true||loadmap[i][j + k] != init-1)
							{ check = false; break; }
						}
						for (int k = 0; k < L; k++) {
							checkrow[j + k] = true;
						}
						if (check == false) break;
						j += L-1; //앞에다가 경사로를 놓았을 경우 점프가 필요
					}
				}
			}
			else {check = false; break;} //높이1차이 이상
		init = loadmap[i][j];
		}
		if (check == true) { result++;  }
	}
}
void looku() {
	for (int i = 0; i < N; i++) {
		initcheck();
		init = loadmap[0][i];
		check = true;
		for (int j = 1; j < N; j++) {
			if (init == loadmap[j][i]) { init = loadmap[j][i]; continue; }
			if (gap(init, loadmap[j][i]) == 1) { //높이1차이
				if (init < loadmap[j][i]) { //벽을 만남(나보다 큰)
					if (j - L < 0) { check = false; break; }
					else {
						for (int k = 1; k <= L; k++) {
							if (checkrow[j - k] == true || loadmap[j - k][i] != init)
							{
								check = false; break;
							}
						}
						for (int k = 1; k <= L; k++) {
							checkrow[j - k] = true;
						}
						if (check == false) break;
					}
				}
				else { //나보다 작은 친구를 만남
					if (j + L > N) { check = false; break; }
					else {
						for (int k = 0; k < L; k++) {
							if (checkrow[j + k] == true || loadmap[j + k][i] != init - 1)
							{
								check = false; break;
							}
						}
						for (int k = 0; k < L; k++) {
							checkrow[j + k] = true;
						}
						if (check == false) break;
						j += L-1; //앞에다가 경사로를 놓았을 경우 점프가 필요
					}
				}
			}
			else { check = false; break; } //높이1차이 이상
			init = loadmap[j][i];
		}
		if (check == true) { result++;  }
	}
}

void checkingload() {
	lookr();
	looku();
	cout << result;
}

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

	cin >> N >> L;
	inputs();
	checkingload();
	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;
}