이것 저것 &

문제링크: www.acmicpc.net/problem/17822

개인적으로 많이 예외를 못찾아서 고민한 문제....

이런 문제일수록 구현을 간단하게 설계해야 한다.

구현해야할 것은 크게 

• 0. 입력
• 1. 원판 돌리기
• 2. 인접한 수 탐색
• 2-1. 인접한 수 지우기
• 2-2.  평균값에서 감산, 가감하기
• 3. 결과 도출

깨알팁 tip)

1. 원판 돌리기 같은경우에 시계 반대 방향은 m - k 번 시계방향으로 돌리는 것과 같다.

2. 인접한 수를 탐색하는 bfs 구현시 배열을 통해서 구현 범위를 줄일 수 있다.

아래는 정답 코드입니다.

#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

int n, m, t;
int arr[51][51] = { 0, };
int result = 0;
int temp[51] = { 0, };
int visited[51][51];

int y_ar[4] = { 1,-1,0,0 };
int x_ar[4] = { 0,0,1,-1 };

//2. search
bool bfs(int y, int x) {

	memset(visited, 0, sizeof(visited));

	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny < 0 || ny == n) continue;

			if (nx == m) nx = 0;
			else if (nx == -1) nx = m - 1;

			if (visited[ny][nx] == 0 && arr[ny][nx] == arr[cy][cx]) {
				que.push(make_pair(ny, nx));
				visited[ny][nx] = visited[cy][cx] + 1;
			}

		}
	}

	//erase
	bool jud = false;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (visited[i][j] > 1)
				jud = true;
	if (jud == true) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (visited[i][j] != 0)
					arr[i][j] = 0;
	}
	return jud;
}

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

	//0. init
	cin >> n >> m >> t;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	while (t--) {
		int x, d, k;
		cin >> x >> d >> k;
		if (d == 1)
			k = m - k;
		//1. 회전
		for (int i = x - 1; i < n; i += x) {
			
			for (int l = 0; l < k; l++) {
				for (int j = 0; j < m; j++)
					temp[j] = arr[i][j];

				for (int j = 1; j < m; j++)
					arr[i][j] = temp[j - 1];
				arr[i][0] = temp[m - 1];
			}
		}



		
		bool jud = false;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				if (visited[i][j] == 0 && arr[i][j] != 0) {
					
					bool temp = bfs(i, j);
					if (temp == true)
						jud = true;
				}
			}

		//평균값 구해서 +1, -1  해주기
		if (jud == false) { 
			double sum = 0;
			double cnt = 0;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					if (arr[i][j] != 0 ) {
						sum += arr[i][j];
						cnt += 1;
					}
			if (cnt > 0) {
				sum = sum / cnt;
				for (int i = 0; i < n; i++)
					for (int j = 0; j < m; j++)
						if (arr[i][j] != 0) {
							if (sum > arr[i][j])
								arr[i][j] ++;
							else if (sum < arr[i][j])
								arr[i][j] --;
						}
			}
		}


	}


	//result
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			result += arr[i][j];
	cout << result << endl;

	
}

문제풀이: www.acmicpc.net/problem/19238

구현 순서는 

• 0. 입력값 받기
• 1. bfs로 이동거리 재기
• 2. 가장 가까운 사람에게 이동
• 3. 목적지까지 거리 도출
• 4. 목적지로 이동

주의할 점은

• 1. 이동과 동시에 도착할때, 즉 택시위치와 사람위치가 같은 경우에는 거리가 0이다.
• 2. 벽으로 막혀있어 택시가 목적지나 사람에게 도달하지 못해도 결과값은 -1이다.
• 3. 목적지에 도착하면서 연료가 바닥나는 것은 괜찮다.

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

typedef struct a {
	int y;
	int x;
}pos;

int n, m, f;
int arr[21][21] = { 0, };
int visited[21][21];
pos taxi;
vector <pos> people;
vector <pos> destination;

int y_ar[4] = { 0,1,0,-1 };
int x_ar[4] = { 1,0,-1,0 };

void bfs(int y, int x) {
	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1; // -1 해야함 

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny >= 1 && ny <= n && nx >= 1 && nx <= n) {
				if (arr[ny][nx] == 0 && visited[ny][nx] == 0) {
					que.push(make_pair(ny, nx));
					visited[ny][nx] = visited[cy][cx] + 1;
				}
			}
		}
	}
}

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

	cin >> n >> m >> f;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> arr[i][j];
	cin >> taxi.y >> taxi.x;
	for (int i = 0; i < m; i++) {
		int t1, t2, t3, t4;
		cin >> t1 >> t2 >> t3 >> t4;
		people.push_back({ t1,t2 });
		destination.push_back({ t3,t4 });
	}

	for (int k = 0; k < m; k++) {
		//1. 이동 거리 측정
		memset(visited, 0, sizeof(visited));
		bfs(taxi.y, taxi.x);
		/*
		for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
		cout << visited[i][j] << ' ';
		cout << endl;
		}*/

		//2. 가장 가까운 사람 선택
		int dis = 1000000000;
		int ny = 0, nx = 0, index = -1;
		for (int i = 0; i < people.size(); i++) {
			int y = people[i].y;
			int x = people[i].x;
			if (visited[y][x] < dis) {
				ny = y;
				nx = x;
				index = i;
				dis = visited[y][x];
			}
			else if (visited[y][x] == dis) {
				if (ny > y) {
					ny = y;
					nx = x;
					index = i;
				}
				else if (nx > x && ny == y) {
					ny = y;
					nx = x;
					index = i;
				}
			}
		}
		people.erase(people.begin() + index);
		taxi.y = ny, taxi.x = nx;
		f -= (visited[ny][nx] - 1);
		if (visited[ny][nx] == 0) {
			f = -1;
			break;
		}
		if (f <= 0)
			break;
		//cout << "y " << ny << "x " << nx << "i " << index << endl;

		//3. 목적지까지 거리 도출
		memset(visited, 0, sizeof(visited));
		bfs(taxi.y, taxi.x);
		//4. 목적지로 이동 
		int dy = destination[index].y;
		int dx = destination[index].x;
		if (visited[dy][dx] == 0) {
			f = -1;
			break;
		}
		taxi.y = dy, taxi.x = dx;
		destination.erase(destination.begin() + index);
		f -= (visited[dy][dx] - 1);
		if (f < 0)
			break;
		f += ((visited[dy][dx] - 1) * 2);
	}


	if (f <= 0)
		cout << -1 << endl;
	else
		cout << f << endl;
	return 0;
}

문제링크: www.acmicpc.net/problem/12996

dp 문제입니다.

아이디어 도출이 어려운 문제지만 구현난이도는 최하입니다.

3명의 친구들이 불러야 하는 곡수와 전체곡의 갯수가 주어지기 때문에 

long long dp[51][51][51][51]; // s,dotorya, kesakiyo, hongjun7 라는 dp배열을 만들어 메모이제이션 하면 됩니다.

dp[s][d][k][h]는 s곡 남았을때, 1번 친구가 d개 남고, 2번 친구가 k개 남고, 3번 친구가 h개 남았을때의 최대값을 저장합니다.

아래는 정답코드입니다. 막상 구현하니 너무 간단하네요.

주의할 점은 long long을 사용해야 한다는것입니다. 

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

long long dp[51][51][51][51]; // s,dotorya, kesakiyo, hongjun7

long long solved(int s, int d, int k, int h) {

	if (s == 0) {
		if (d == 0 && k == 0 && h == 0)
			return 1;
		else
			return 0;
	}
	
	long long& ret = dp[s][d][k][h];
	if (ret != -1)
		return ret;
	ret = 0;

	ret += solved(s - 1, d - 1, k, h);
	ret += solved(s - 1, d, k - 1, h);
	ret += solved(s - 1, d, k, h - 1);

	ret += solved(s - 1, d - 1, k - 1, h);
	ret += solved(s - 1, d - 1, k, h - 1);
	ret += solved(s - 1, d, k - 1, h - 1);

	ret += solved(s - 1, d - 1, k - 1, h - 1);

	ret %= 1000000007;
	return ret;
}

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

	int s, d, k, h;
	cin >> s >> d >> k >> h;

	memset(dp, -1, sizeof(dp));
	cout << solved(s, d, k, h) << endl;

	return 0;
}

문제풀이: www.acmicpc.net/problem/14567

전형적인 비트마스킹(up-down) 문제입니다.

재귀함수를 사용하되, 배열에 방문값들을 저장하는 형태로 풀어나가면 됩니다! 

아래는 정답코드입니다.

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

int n = 0, m = 0;
vector <int> vec[1001];
int dp[1001] = {0, };

int solved(int num) {
	if (vec[num].size() == 0)
		return 1;
	int& ret = dp[num];
	if (ret != 0) return ret;

	ret = 1;
	for (int i = 0; i < vec[num].size(); i++) {
		ret = max(ret, solved(vec[num][i]) + 1);
	}

	return ret;
}

int main() {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		vec[t2].push_back(t1);
	}

	for (int i = 1; i <= n; i++) {
		cout << solved(i) << ' ';
	}
	cout << endl;
}

문제링크:www.acmicpc.net/problem/17404

전형적인 dp문제입니다.

근데 문제조건처럼 1과 n이 연결되어 있다는 것을 인지해야합니다.

구현방법은 간단합니다.

첫번째의 시작점을 정해두고 dp를 구하면 됩니다. 이렇게 3번 반복하며 시작점과 끝점의 값이 다르도록 구현하는 것이 핵심입니다.

위 설명과 아래 주석을 함께 보시면 이해하는데 어려움 없을 겁니다!

아래는 정답코드입니다.

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


int n = 0, result = 1000000000;
int arr[1001][3] = { 0, };
int dp[1001][3] = { 0, };

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

	cin >> n;
	for (int i = 1; i <= n; i++)
		for(int j=0;j<3;j++)
			cin >> arr[i][j];

	for (int k = 0; k < 3; k++) {

		//1. 초기값 설정
		for (int i = 0; i < 3; i++)
			dp[1][i] = 1000000000;
		dp[1][k] = arr[1][k];

		
		//2. 이후 계산
		for (int i = 2; i <= n; i++) {
			dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = arr[i][1] + min(dp[i - 1][2], dp[i - 1][0]);
			dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
		}

		//3. 초기값이 아닌 경우에만 result 도출
		for (int i = 0; i < 3; i++) {
			if (k == i) continue;
			result = min(result, dp[n][i]);
		}
	}

	cout << result << endl;
	return 0;
}

문제링크: www.acmicpc.net/problem/20058

삼성 코딩테스트 문제입니다.

구현해야하는 항목이 많아서 번거로운 문제였지만, 구현자체의 난이도는 어려운 문제가 아닙니다.

이런 문제일수록 항목별로 나눠 구현하고 중간중간에 디버깅을 해보면서 정상적으로 동작해야 하는지 확인해야 힙니다.

크게 구현할 내용은

• 1. 입력값 받기
• 2. 구역 범위 나누기
• 3. 90도 회전시키기
• 4. 얼음 녹이기
• 5. 결과값 도출하기

입니다. 

구역 범위는 구획의 크기별로 2중포문을 통해 구현하면 됩니다. 

90도 회전은 temp라는 임시배열을 생성하고 해당 배열에 90도 돌려서 옮겨주면 됩니다. 

이때 모든 부분을 90로 회전하기 때문에 len, y, x 값을 줄이며 반복해줍니다.

얼음 녹이기는 4방향을 비교하며 해결하였고

결과값 도출시에는 bfs를 사용하여 하나의 덩어리합을 구했습니다.

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int arr[100][100] = { 0, };
int temp[100][100] = { 0, };
int visited[100][100] = { 0, };

int n, q;
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
int result1 = 0, result2 = 0;

void rotate(int sy, int sx, int v) {
	int y = sy;
	int x = sx;
	int len = v;

	while (len > 1) {


		for (int i = y, j = 1; j <= len; j++, i++) {  //1
			temp[y][x + len - j] = arr[i][x];
		}

		for (int i = x, j = 0; j < len; j++, i++) { //2
			temp[y + j][x] = arr[y + len - 1][i];
		}

		for (int i = y + len - 1, j = 0; j < len; j++, i--) {  //3
			temp[y + len - 1][x + j] = arr[i][x + len - 1];
		}


		for (int i = x + len - 1, j = 1; j <= len; j++, i--) { //4
			temp[y + len - j][x + len - 1] = arr[y][i];
		}


		y++;
		x++;
		len -= 2;
	}

}

int bfs(int y, int x, int len) {
	visited[y][x] = 1;
	int result = 1;
	queue <pair <int, int>> que;
	que.push(make_pair(y, x));

	while (!que.empty()) {

		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny >= 1 && ny <= len && nx >= 1 && nx <= len && visited[ny][nx] == 0 && arr[ny][nx] > 0) {
				visited[ny][nx] = 1;
				result++;
				que.push(make_pair(ny, nx));
			}

		}
	}

	return result;

}

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

	//0. input
	cin >> n >> q;
	int len = 1;
	for (int i = 0; i < n; i++)
		len *= 2;
	for (int i = 1; i <= len; i++)
		for (int j = 1; j <= len; j++)
			cin >> arr[i][j];

	for (int k = 0; k < q; k++) {
		int temp1;
		cin >> temp1;
		if (temp1 != 0) { //0이 아닐 때 
			int v = 1;
			for (int i = 0; i < temp1; i++)
				v *= 2;
			//1. divide
			memset(temp, 0, sizeof(temp));
			for (int i = 1; i < len; i += v)
				for (int j = 1; j < len; j += v) {
					//2. rotate
					rotate(i, j, v);
				}
			for (int i = 1; i <= len; i++)
				for (int j = 1; j <= len; j++)
					arr[i][j] = temp[i][j];
		}

		//3. erase ice

		memset(temp, 0, sizeof(temp));

		for (int i = 1; i <= len; i++)
			for (int j = 1; j <= len; j++) {
				temp[i][j] = arr[i][j];
				int zero_ = 0;
				for (int u = 0; u < 4; u++) {
					if (arr[i + y_ar[u]][j + x_ar[u]] != 0)
						zero_++;
				}
				if (zero_ < 3 && arr[i][j] > 0) {
					temp[i][j] --;
				}
			}
		for (int i = 1; i <= len; i++)
			for (int j = 1; j <= len; j++)
				arr[i][j] = temp[i][j];

		/*
		cout << endl;
		for (int i = 1; i <= len; i++) {
		for (int j = 1; j <= len; j++)
		cout << arr[i][j] << ' ';
		cout << endl;
		}*/

	}

	//4. result

	for (int i = 1; i <= len; i++)
		for (int j = 1; j <= len; j++) {
			result1 += arr[i][j];
			if (visited[i][j] == 0 && arr[i][j] > 0)
				result2 = max(result2, bfs(i, j, len));
		}



	cout << result1 << endl;
	cout << result2 << endl;
}

문제링크:www.acmicpc.net/problem/20057

20년도 하반기 삼성 코딩테스트 기출문제입니다.

저는 오전에 풀어서 접하지 못했던 문제입니다. 

우선 크게 구현해야하는 부분이 4가지 였습니다.

• 1. 입력 받기
• 2. 회전시키기
• 3. 모래 이동
• 4. 결과 도출

2, 3번이 핵심입니다.

우선 회전은 for문과 y_ar, x_ar(방향배열)을 통해서 구현했습니다.

가운데 점부터 시작하여 방향별로 cnt 갯수만큼 점을 옮겨줌으로서 2번 회전을 구현했습니다.

그렇다면 3번 모래 이동은 어떤식으로 구현할까요?

저는 구조체를 하나 생성했습니다.

typedef struct a {
	vector <int> vec;
	double per;

}moved;

해당 구조체에 vec에는 모래가 이동하는 좌표로 가기위해 필요 값들을 그리고 per에는 해당 좌표에 대한 퍼센트를 기입해놓았습니다. 현재 방향에 따라서 값을 더해주는 형태로 구현했기 때문에 아래처럼 간단하게 구현할 수 있었습니다.

아래는 정답코드입니다. 해당 문제에서 주의할 점은 수의 범위가 넘어갈 때에는 예외처리를 통해서 데이터를 지우게끔 해야하는 것입니다. 

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

typedef struct a {
	vector <int> vec;
	double per;

}moved;

int n = 0, result =0;
int arr[501][501] = { 0, };
moved val[9];
int y_ar[4] = { 0,1,0,-1 };
int x_ar[4] = { -1,0,1,0 };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//init
	val[0].vec.push_back(1), val[0].per = 0.01;
	val[1].vec.push_back(3), val[1].per = 0.01;
	val[2].vec.push_back(1), val[2].vec.push_back(0), val[2].per = 0.07;
	val[3].vec.push_back(3), val[3].vec.push_back(0), val[3].per = 0.07;
	val[4].vec.push_back(1), val[4].vec.push_back(1), val[4].vec.push_back(0), val[4].per = 0.02;
	val[5].vec.push_back(3), val[5].vec.push_back(3), val[5].vec.push_back(0), val[5].per = 0.02;
	val[6].vec.push_back(1), val[6].vec.push_back(0), val[6].vec.push_back(0), val[6].per = 0.1;
	val[7].vec.push_back(3), val[7].vec.push_back(0), val[7].vec.push_back(0), val[7].per = 0.1;
	val[8].vec.push_back(0), val[8].vec.push_back(0), val[8].vec.push_back(0), val[8].per = 0.05;
	//0.
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			result += arr[i][j];
		}
	
	//1. rotate
	int cy = n / 2 + 1, cx = n / 2 + 1, dir = 0, cnt = 0;
	for (int k = 0; k < n * 2 - 1; k++) {
		if (k % 2 == 0)
			cnt++;
		for (int i = 0; i < cnt; i++) { // 해당방향으로 이동
			int curval = arr[cy + y_ar[dir]][cx + x_ar[dir]];

			for (int j = 0; j < 9; j++) {
				int ny = cy;
				int nx = cx;
				for (int u = 0; u < val[j].vec.size(); u++) {
					ny += y_ar[(dir + val[j].vec[u]) % 4];
					nx += x_ar[(dir + val[j].vec[u]) % 4];
				}
				if (ny >= 1 && ny <= n && nx >= 1 && nx <= n) {
					arr[ny][nx] += (int)(curval * val[j].per);
				}
				arr[cy + y_ar[dir]][cx + x_ar[dir]] -= (int)(curval * val[j].per);

			}
			//알파 계산 
			if (cy + y_ar[dir] * 2 >= 1 && cy + y_ar[dir] * 2 <= n && cx + x_ar[dir] * 2 >= 1 && cx + x_ar[dir] * 2 <= n) 
				arr[cy + y_ar[dir] * 2][cx + x_ar[dir] * 2] += arr[cy + y_ar[dir]][cx + x_ar[dir]];
			
			if(cy + y_ar[dir] >= 1 && cy + y_ar[dir] <= n && cx + x_ar[dir] >= 1 && cx + x_ar[dir] <= n)
				arr[cy + y_ar[dir]][cx + x_ar[dir]] = 0;

			cy += y_ar[dir], cx += x_ar[dir]; // 실제 좌표 이동

			/*
			cout << endl;
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++)
					cout << arr[i][j] << ' ';
				cout << endl;
			}*/
		}
		
		dir++;
		if (dir == 4)
			dir = 0;

		
	}





	int sum = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) 
			sum += arr[i][j];	
	result -= sum;
	cout << result << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/20055

20년도 하반기 삼성 코딩테스트 기출문제입니다.

저는 실제 코딩테스트로 먼저 접했던 문제입니다.

문제는 거의 비슷하고, 코딩테스트에서는 더 자세하게 설명해줍니다.

해야하는 일들을 순서대로 구현하면 되는 시뮬레이션 문제입니다.

1. 벨트가 한 칸 회전한다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
   1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

4가지를 반복하며 결과를 도출하면 됩니다.

저는 dequeue 를 사용하지 않고 단순 배열을 이용해서 구현했습니다.

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

int n = 0, k = 0;
int arr[201][2] = { 0, };
int cnt = 1;
vector <int> vec;


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


	//0.
	cin >> n >> k;
	for (int i = 1; i <= 2 * n; i++)
		cin >> arr[i][0];

	while (1) {
		//1.
		int temp = arr[2 * n][0];
		int temp2 = arr[2 * n][1];

		if (arr[n][1] == 1) { // 나갈친구 미리 제거
			arr[n][1] = 0;
		}
		for (int i = 2 * n; i > 1; i--) {
			arr[i][0] = arr[i - 1][0];
			arr[i][1] = arr[i - 1][1];
		}
		arr[1][0] = temp;
		arr[1][1] = temp2;
		
		//로봇도 이동시켜줘야지
		for (int i = 0; i < vec.size(); i++) {
			if (vec[i] < n)
				vec[i]++;
			else if (vec[i] == n) {
				//arr[vec[i] + 1][1] = 0;
				vec.erase(vec.begin() + i);
				i--;
			}
		}


		//2. 
		for (int i = 0; i < vec.size(); i++) {
			int x = vec[i];
			if (x < n && arr[x + 1][0] > 0 && arr[x + 1][1] == 0) {
				
				arr[x + 1][0]--;
				arr[x + 1][1] = 1; //로봇이 있다.// 로봇이 있음 1 없음 0 
				arr[x][1] = 0; // 이제 없다. 
				vec[i]++;
			}
			else if (x == n) {
				arr[x][1] = 0;
				vec.erase(vec.begin() + i);
				i--;
			}
		}

		//3.
		if (arr[1][1] == 0 && arr[1][0] > 0) {
			arr[1][0]--;
			arr[1][1] = 1;
			vec.push_back(1);
		}
		//4. 
		int v = 0;
		for (int i = 1; i <= 2 * n; i++) {
			if (arr[i][0] == 0)
				v++;
		}
		if (v >= k) {
			cout << cnt << endl;
			return 0;
		}
		cnt++;



	}



	return 0;
}