728x90

www.acmicpc.net/problem/2146

 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

www.acmicpc.net

BFS로 섬을 체크하고 가장 짧은 다리를 놓기 위해 또 한 번 더 BFS를 해줘야 한다.

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

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<vector<int>> v(n, vector<int>(n));
	vector<vector<bool>> visited(n, vector<bool>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	int number = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j] && v[i][j] == 1) {
				queue<pair<int, int>> q;
				q.push(make_pair(i, j));
				while (!q.empty()) {
					pair<int, int> cur = q.front();
					q.pop();
					v[cur.first][cur.second] = number;
					if (!visited[cur.first][cur.second]) {
						visited[cur.first][cur.second] = true;
						for (int i = 0; i < 4; i++) {
							int row = cur.first + dx[i];
							int col = cur.second + dy[i];
							if (row < n && row >= 0 && col < n && col >= 0 && v[row][col] == 1) {
								q.push(make_pair(row, col));
							}
						}
					}
				}
				number++;
			}
		}
	}
	int minDistance = 100000;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (v[i][j] != 0) {
				visited = vector<vector<bool>>(n, vector<bool>(n, false));
				int start = v[i][j];
				queue<tuple<int, int, int>> q;
				q.push(make_tuple(i, j, 0));
				while (!q.empty()) {
					tuple<int, int, int> cur = q.front();
					q.pop();
					if (v[get<0>(cur)][get<1>(cur)] != 0 && v[get<0>(cur)][get<1>(cur)] != start) {
						if (get<2>(cur) - 1 < minDistance)
							minDistance = get<2>(cur) - 1;
						break;
					}
					if (!visited[get<0>(cur)][get<1>(cur)]) {
						visited[get<0>(cur)][get<1>(cur)] = true;
						for (int i = 0; i < 4; i++) {
							int row = get<0>(cur) + dx[i];
							int col = get<1>(cur) + dy[i];
							int distance = get<2>(cur);
							if (row < n && row >= 0 && col < n && col >= 0 && v[row][col] != start) {
								q.push(make_tuple(row, col, distance + 1));
							}
						}
					}
				}
			}
		}
	}
	cout << minDistance;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 15684번 사다리 조작  (0) 2021.01.22
[백준] 2573번 빙산  (0) 2021.01.21
[백준] 16236번 아기 상어  (0) 2021.01.21
[백준] 13460번 구슬 탈출 2  (0) 2021.01.20
[백준] 2458번 키 순서  (0) 2021.01.19
728x90

www.acmicpc.net/problem/16236

 

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

BFS로 풀었다. 주의할 것은

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

이 조건이다.

따라서 BFS로 탐색을 하다가 최단 거리로 이동할 수 있는 칸을 발견한다고 바로 거기로 이동하면 안 된다.

그 최단거리로 이동할 수 있는 칸들을 temp에 저장해주고 행, 열을 기준으로 오름차순 정렬을 하여 첫 번째 원소로 이동하도록 하였다.

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

int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, row, col, size;
	cin >> n;
	vector<vector<int>> v(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
			if (v[i][j] == 9) {
				row = i;
				col = j;
				v[i][j] = 0;
			}
		}
	}
	size = 2;
	int cnt = 0;
	int totalSecond = 0;
	while (true) {
		queue<tuple<int, int, int>> q;
		vector<vector<bool>> visited(n, vector<bool>(n, false));
		q.push(make_tuple(row, col, 0));
		int minDistance = 100000;
		vector<pair<int, int>> temp;
		while (!q.empty()) {
			tuple<int, int, int> cur = q.front();
			q.pop();
			if (v[get<0>(cur)][get<1>(cur)] > 0 && v[get<0>(cur)][get<1>(cur)] < size && get<2>(cur) <= minDistance) {
				minDistance = get<2>(cur);
				temp.push_back(make_pair(get<0>(cur), get<1>(cur)));
			}
			if (!visited[get<0>(cur)][get<1>(cur)] && get<2>(cur) <= minDistance) {
				visited[get<0>(cur)][get<1>(cur)] = true;
				for (int i = 0; i < 4; i++) {
					int r = get<0>(cur) + dx[i];
					int c = get<1>(cur) + dy[i];
					int time = get<2>(cur);
					if (r >= 0 && r < n && c >= 0 && c < n) {
						if (v[r][c] <= size) {
							q.push(make_tuple(r, c, time + 1));
						}
					}
				}
			}
		}
		sort(temp.begin(), temp.end());
		if (temp.size() == 0) {
			break;
		}
		else {
			row = temp[0].first;
			col = temp[0].second;
			totalSecond += minDistance;
			cnt++;
			if (cnt == size) {
				size++;
				cnt = 0;
			}
			v[row][col] = 0;
		}
	}
	cout << totalSecond;
	return 0;
}

www.acmicpc.net/problem/16236

 

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

 

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2573번 빙산  (0) 2021.01.21
[백준] 2146번 다리 만들기  (0) 2021.01.21
[백준] 13460번 구슬 탈출 2  (0) 2021.01.20
[백준] 2458번 키 순서  (0) 2021.01.19
[백준] 16234번 인구 이동  (0) 2021.01.18
728x90

www.acmicpc.net/problem/13460

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

BFS로 풀었다. 코드가 너무 더럽지만... 어쨌든 스스로 힘으로 풀어서 맞았다.

방문체크는 map을 이용했다.

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <tuple>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	pair<int, int> blue;
	pair<int, int> red;
	vector<vector<char>> v(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
			if (v[i][j] == 'B') {
				blue = make_pair(i, j);
				v[i][j] = '.';
			}
			else if (v[i][j] == 'R') {
				red = make_pair(i, j);
				v[i][j] = '.';
			}
		}
	}
	map<pair<pair<int, int>, pair<int, int>>, int> visited; // 빨, 파
	queue<tuple<pair<int, int>, pair<int, int>, int>> q;
	q.push(make_tuple(red, blue, 0));
	int answer = -1;
	while (!q.empty()) {
		tuple<pair<int, int>, pair<int, int>, int> cur = q.front();
		q.pop();
		int redRow = get<0>(cur).first;
		int redCol = get<0>(cur).second;
		int blueRow = get<1>(cur).first;
		int blueCol = get<1>(cur).second;
		int cnt = get<2>(cur);
		int tempRedRow;
		int tempRedCol;
		int tempBlueRow;
		int tempBlueCol;
		int flag;
		if (cnt < 10 && !visited[make_pair(get<0>(cur), get<1>(cur))]) {
			visited[make_pair(get<0>(cur), get<1>(cur))] = true;
			// 위
			tempRedRow = redRow;
			tempBlueRow = blueRow;
			flag = true;
			if (redCol == blueCol) {
				if (redRow > blueRow) {
					while (tempBlueRow >= 1) {
						char next = v[tempBlueRow - 1][blueCol];
						if (next == 'O') {
							flag = false;
							tempBlueRow--;
							break;
						}
						else if (next == '.') {
							tempBlueRow--;
						}
						else {
							break;
						}
					}
					while (tempRedRow >= 1) {
						char next = v[tempRedRow - 1][redCol];
						if (next != 'O' && tempRedRow - 1 == tempBlueRow)
							break;
						if (next == 'O') {
							answer = cnt + 1;
							tempRedRow--;
							break;
						}
						else if (next == '.') {
							tempRedRow--;
						}
						else {
							break;
						}
					}
				}
				else {
					while (tempRedRow >= 1) {
						char next = v[tempRedRow - 1][redCol];
						if (next == 'O') {
							answer = cnt + 1;
							tempRedRow--;
							break;
						}
						else if (next == '.') {
							tempRedRow--;
						}
						else {
							break;
						}
					}
					while (tempBlueRow >= 1) {
						char next = v[tempBlueRow - 1][blueCol];
						if (next != 'O' && tempBlueRow - 1 == tempRedRow)
							break;
						if (next == 'O') {
							flag = false;
							tempBlueRow--;
							break;
						}
						else if (next == '.') {
							tempBlueRow--;
						}
						else {
							break;
						}
					}
				}
				if (answer != -1) {
					if (!flag)
						answer = -1;
					if (answer != -1)
						break;
				}
				if (tempRedRow == redRow && tempBlueRow == blueRow)
					flag = false;
				if (flag) {
					q.push(make_tuple(make_pair(tempRedRow, redCol), make_pair(tempBlueRow, blueCol), cnt + 1));
				}
			}
			else {
				while (tempRedRow >= 1) {
					char next = v[tempRedRow - 1][redCol];
					if (next == 'O') {
						answer = cnt + 1;
						tempRedRow--;
						break;
					}
					else if (next == '.') {
						tempRedRow--;
					}
					else {
						break;
					}
				}
				while (tempBlueRow >= 1) {
					char next = v[tempBlueRow - 1][blueCol];
					if (next == 'O') {
						flag = false;
						tempBlueRow--;
						break;
					}
					else if (next == '.') {
						tempBlueRow--;
					}
					else {
						break;
					}
				}
			}
			if (answer != -1) {
				break;
			}
			if (tempRedRow == redRow && tempBlueRow == blueRow)
				flag = false;
			if (flag) {
				q.push(make_tuple(make_pair(tempRedRow, redCol), make_pair(tempBlueRow, blueCol), cnt + 1));
			}
			// 아래
			tempRedRow = redRow;
			tempBlueRow = blueRow;
			flag = true;
			if (redCol == blueCol) {
				if (redRow < blueRow) {
					while (tempBlueRow < n - 1) {
						char next = v[tempBlueRow + 1][blueCol];
						if (next == 'O') {
							flag = false;
							tempBlueRow++;
							break;
						}
						else if (next == '.') {
							tempBlueRow++;
						}
						else {
							break;
						}
					}
					while (tempRedRow < n - 1) {
						char next = v[tempRedRow + 1][redCol];
						if (next != 'O' && tempRedRow + 1 == tempBlueRow)
							break;
						if (next == 'O') {
							answer = cnt + 1;
							tempRedRow++;
							break;
						}
						else if (next == '.') {
							tempRedRow++;
						}
						else {
							break;
						}
					}
				}
				else {
					while (tempRedRow < n - 1) {
						char next = v[tempRedRow + 1][redCol];
						if (next == 'O') {
							answer = cnt + 1;
							tempRedRow++;
							break;
						}
						else if (next == '.') {
							tempRedRow++;
						}
						else {
							break;
						}
					}
					while (tempBlueRow < n - 1) {
						char next = v[tempBlueRow + 1][blueCol];
						if (next != 'O' && tempBlueRow + 1 == tempRedRow)
							break;
						if (next == 'O') {
							flag = false;
							tempBlueRow++;
							break;
						}
						else if (next == '.') {
							tempBlueRow++;
						}
						else {
							break;
						}
					}
				}
				if (answer != -1) {
					if (!flag)
						answer = -1;
					if (answer != -1)
						break;
				}
				if (tempRedRow == redRow && tempBlueRow == blueRow)
					flag = false;
				if (flag) {
					q.push(make_tuple(make_pair(tempRedRow, redCol), make_pair(tempBlueRow, blueCol), cnt + 1));
				}
			}
			else {
				while (tempRedRow < n - 1) {
					char next = v[tempRedRow + 1][redCol];
					if (next == 'O') {
						answer = cnt + 1;
						tempRedRow++;
						break;
					}
					else if (next == '.') {
						tempRedRow++;
					}
					else {
						break;
					}
				}
				while (tempBlueRow < n - 1) {
					char next = v[tempBlueRow + 1][blueCol];
					if (next == 'O') {
						flag = false;
						tempBlueRow++;
						break;
					}
					else if (next == '.') {
						tempBlueRow++;
					}
					else {
						break;
					}
				}
			}
			if (tempRedRow == redRow && tempBlueRow == blueRow)
				flag = false;
			if (answer != -1) {
				break;
			}
			if (flag) {
				q.push(make_tuple(make_pair(tempRedRow, redCol), make_pair(tempBlueRow, blueCol), cnt + 1));
			}
			// 왼쪽
			tempRedCol = redCol;
			tempBlueCol = blueCol;
			flag = true;
			if (redRow == blueRow) {
				if (redCol > blueCol) {
					while (tempBlueCol >= 1) {
						char next = v[blueRow][tempBlueCol - 1];
						if (next == 'O') {
							flag = false;
							tempBlueCol--;
							break;
						}
						else if (next == '.') {
							tempBlueCol--;
						}
						else {
							break;
						}
					}
					while (tempRedCol >= 1) {
						char next = v[redRow][tempRedCol - 1];
						if (next != 'O' && tempRedCol - 1 == tempBlueCol)
							break;
						if (next == 'O') {
							answer = cnt + 1;
							tempRedCol--;
							break;
						}
						else if (next == '.') {
							tempRedCol--;
						}
						else {
							break;
						}
					}
				}
				else {
					while (tempRedCol >= 1) {
						char next = v[redRow][tempRedCol - 1];
						if (next == 'O') {
							answer = cnt + 1;
							tempRedCol--;
							break;
						}
						else if (next == '.') {
							tempRedCol--;
						}
						else {
							break;
						}
					}
					while (tempBlueCol >= 1) {
						char next = v[blueRow][tempBlueCol - 1];
						if (next != 'O' && tempBlueCol - 1 == tempRedCol)
							break;
						if (next == 'O') {
							flag = false;
							tempBlueCol--;
							break;
						}
						else if (next == '.') {
							tempBlueCol--;
						}
						else {
							break;
						}
					}
				}
				if (answer != -1) {
					if (!flag)
						answer = -1;
					if (answer != -1)
						break;
				}
				if (tempRedCol == redCol && tempBlueCol == blueCol)
					flag = false;
				if (flag) {
					q.push(make_tuple(make_pair(redRow, tempRedCol), make_pair(blueRow, tempBlueCol), cnt + 1));
				}
			}
			else {
				while (tempRedCol >= 1) {
					char next = v[redRow][tempRedCol - 1];
					if (next == 'O') {
						answer = cnt + 1;
						tempRedCol--;
						break;
					}
					else if (next == '.') {
						tempRedCol--;
					}
					else {
						break;
					}
				}
				while (tempBlueCol >= 1) {
					char next = v[blueRow][tempBlueCol - 1];
					if (next == 'O') {
						flag = false;
						tempBlueCol--;
						break;
					}
					else if (next == '.') {
						tempBlueCol--;
					}
					else {
						break;
					}
				}
			}
			if (answer != -1) {
				break;
			}
			if (tempRedCol == redCol && tempBlueCol == blueCol)
				flag = false;
			if (flag) {
				q.push(make_tuple(make_pair(redRow, tempRedCol), make_pair(blueRow, tempBlueCol), cnt + 1));
			}
			// 오른쪽
			tempRedCol = redCol;
			tempBlueCol = blueCol;
			flag = true;
			if (redRow == blueRow) {
				if (redCol < blueCol) {
					while (tempBlueCol < m - 1) {
						char next = v[blueRow][tempBlueCol + 1];
						if (next == 'O') {
							flag = false;
							tempBlueCol++;
							break;
						}
						else if (next == '.') {
							tempBlueCol++;
						}
						else {
							break;
						}
					}
					while (tempRedCol < m - 1) {
						char next = v[redRow][tempRedCol + 1];
						if (next != 'O' && tempRedCol + 1 == tempBlueCol)
							break;
						if (next == 'O') {
							answer = cnt + 1;
							tempRedCol++;
							break;
						}
						else if (next == '.') {
							tempRedCol++;
						}
						else {
							break;
						}
					}
				}
				else {
					while (tempRedCol < m - 1) {
						char next = v[redRow][tempRedCol + 1];
						if (next == 'O') {
							tempRedCol++;
							answer = cnt + 1;
							break;
						}
						else if (next == '.') {
							tempRedCol++;
						}
						else {
							break;
						}
					}
					while (tempBlueCol < m - 1) {
						char next = v[blueRow][tempBlueCol + 1];
						if (next != 'O' && tempBlueCol + 1 == tempRedCol)
							break;
						if (next == 'O') {
							flag = false;
							tempBlueCol++;
							break;
						}
						else if (next == '.') {
							tempBlueCol++;
						}
						else {
							break;
						}
					}
				}
				if (answer != -1) {
					if (!flag)
						answer = -1;
					if (answer != -1)
						break;
				}
				if (tempRedCol == redCol && tempBlueCol == blueCol)
					flag = false;
				if (flag) {
					q.push(make_tuple(make_pair(redRow, tempRedCol), make_pair(blueRow, tempBlueCol), cnt + 1));
				}
			}
			else {
				while (tempRedCol < m - 1) {
					char next = v[redRow][tempRedCol + 1];
					if (next == 'O') {
						answer = cnt + 1;
						tempRedCol++;
						break;
					}
					else if (next == '.') {
						tempRedCol++;
					}
					else {
						break;
					}
				}
				while (tempBlueCol >= 1) {
					char next = v[blueRow][tempBlueCol + 1];
					if (next == 'O') {
						flag = false;
						tempBlueCol++;
						break;
					}
					else if (next == '.') {
						tempBlueCol++;
					}
					else {
						break;
					}
				}
			}
			if (answer != -1) {
				break;
			}
			if (tempRedCol == redCol && tempBlueCol == blueCol)
				flag = false;
			if (flag) {
				q.push(make_tuple(make_pair(redRow, tempRedCol), make_pair(blueRow, tempBlueCol), cnt + 1));
			}
		}
	}
	cout << answer;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2146번 다리 만들기  (0) 2021.01.21
[백준] 16236번 아기 상어  (0) 2021.01.21
[백준] 2458번 키 순서  (0) 2021.01.19
[백준] 16234번 인구 이동  (0) 2021.01.18
[백준] 1339번 단어 수학  (0) 2021.01.18
728x90

www.acmicpc.net/problem/2458

 

2458번: 키 순서

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여

www.acmicpc.net

DFS(깊이 우선 탐색)로 풀었다.

일단 정점이 N개인 방향그래프를 만들어준다.

a, b를 입력받으면 a에서 b로 가는 간선을 추가해준다.

그럼 위와 같은 그래프가 만들어질 것이다.

위의 그래프에서 4번 학생만 자신의 키가 몇 번째로 큰지 알 수 있다.

그 이유는 정점 1, 3, 5는 4에 도달할 수 있고 정점 2, 6은 4에서 도달할 수 있는 정점들이기 때문이다.

도달할 수 있는지 없는지는 DFS를 통해 알 수 있다.

그렇게 DFS를 통해 알아낸 도달할 수 있는지 여부는 approach를 완성한다.

i행 j열은 i에서 j로 갈 수 있는지 여부이다.

4행과 4열에서 true의 개수가 6개이다. 그러므로 4번 학생은 몇 번째로 키가 큰지 알 수 있다.

4행에서 쭉 세고 4열에서 쭉 세면 4행 4열은 중복으로 세어지므로 true인 것의 개수는 7이다.

세어줄 때는 i행 i열은 중복으로 세어지므로 i행에서 true의 개수를 쭉 세고 i열에서 true의 개수를 세었을 때

N + 1개이면 i번 학생은 몇 번째로 키가 큰지 알 수 있는 것이다.

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	int a, b;
	vector<int> graph[501];
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
	}
	vector<bool> visited(n + 1, false);
	vector<vector<bool>> approach(n + 1, vector<bool>(n + 1, false));
	for (int i = 1; i <= n; i++) {
		visited = vector<bool>(n + 1, false);
		stack<int> stack;
		stack.push(i);
		while (!stack.empty()) {
			int cur = stack.top();
			stack.pop();
			if (!visited[cur]) {
				visited[cur] = true;
				approach[i][cur] = true;
				for (int j = 0; j < graph[cur].size(); j++) {
					stack.push(graph[cur][j]);
				}
			}
		}
	}
	int answer = 0;
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (approach[i][j])
				cnt++;
			if (approach[j][i])
				cnt++;
		}
		if (cnt == n + 1) {
			answer++;
		}
	}
	cout << answer;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 16236번 아기 상어  (0) 2021.01.21
[백준] 13460번 구슬 탈출 2  (0) 2021.01.20
[백준] 16234번 인구 이동  (0) 2021.01.18
[백준] 1339번 단어 수학  (0) 2021.01.18
[백준] 5014번 스타트링크  (0) 2021.01.18
728x90

www.acmicpc.net/problem/16234

 

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모

www.acmicpc.net

DFS로 풀었다. BFS나 DFS나 아무거나로 풀어도 된다.

DFS는 연합을 만드는 과정이다. 상하좌우 탐색하면서 l개 이상 r개 이하로 차이가 나면 스택에 넣어주었다.

탐색을 하면서 그 연합에 속하는 나라의 행과 열을 pair로 묶어서 countries라는 벡터에 넣어줬다.

또한 그 연합에 속하는 나라의 인구 수를 sum에 누적해서 더해줬다.

그렇게 연합을 만든 후에 sum을 countries.size()로 나눠서 인구 수를 갱신해주었다.

countries.size()가 1이면 인구 이동이 일어나지 않는 것이고 1보다 크면 인구 이동이 일어났다는 것이므로 flag = true로 해준다.

flag가 false라는 것은 더 이상 인구 이동이 일어나지 않는다는 것이므로 while문을 빠져나온다.

가장 바깥쪽 while문은 인구이동이 몇 번 일어났는지를 세어준다.

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, l, r;
	cin >> n >> l >> r;
	vector<vector<int>> v(n, vector<int>(n));
	vector<vector<bool>> visited(n, vector<bool>(n, false));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	int moveCount = 0;
	while (true) {
		visited = vector<vector<bool>>(n, vector<bool>(n, false));
		bool flag = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					stack<pair<int, int>> stack;
					stack.push(make_pair(i, j));
					int sum = 0;
					vector<pair<int, int>> countries;
					while (!stack.empty()) {
						pair<int, int> cur = stack.top();
						stack.pop();
						int row = cur.first;
						int col = cur.second;
						if (!visited[row][col]) {
							visited[row][col] = true;
							sum += v[row][col];
							countries.push_back(cur);
							if (row + 1 < n && abs(v[row][col] - v[row + 1][col]) >= l && abs(v[row][col] - v[row + 1][col]) <= r) {
								stack.push(make_pair(row + 1, col));
							}
							if (row - 1 >= 0 && abs(v[row][col] - v[row - 1][col]) >= l && abs(v[row][col] - v[row - 1][col]) <= r) {
								stack.push(make_pair(row - 1, col));
							}
							if (col + 1 < n && abs(v[row][col] - v[row][col + 1]) >= l && abs(v[row][col] - v[row][col + 1]) <= r) {
								stack.push(make_pair(row, col + 1));
							}
							if (col - 1 >= 0 && abs(v[row][col] - v[row][col - 1]) >= l && abs(v[row][col] - v[row][col - 1]) <= r) {
								stack.push(make_pair(row, col - 1));
							}
						}
					}
					if (countries.size() > 1) {
						flag = true;
						for (int k = 0; k < countries.size(); k++) {
							int row = countries[k].first;
							int col = countries[k].second;
							v[row][col] = sum / countries.size();
						}
					}
				}
			}
		}
		if (!flag)
			break;
		moveCount++;
	}
	cout << moveCount;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 13460번 구슬 탈출 2  (0) 2021.01.20
[백준] 2458번 키 순서  (0) 2021.01.19
[백준] 1339번 단어 수학  (0) 2021.01.18
[백준] 5014번 스타트링크  (0) 2021.01.18
[백준] 12100번 2048 (Easy)  (0) 2021.01.18
728x90

www.acmicpc.net/problem/1339

 

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

무조건 높은 자리에 있는 알파벳이 큰 수인게 좋은 것이 아니다.

입력이 다음과 같이 들어오는 경우

10 
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

A가 100의 자리 수이므로 A가 클수록 좋다고 생각할 수 있지만

A=9, B=8이면 1780이지만 A=8, B=9이면 1790이다.

알파벳별로

1의 자리, 10의 자리, 100의 자리 순서대로 돌면서

1의 자리는 1의 자리수 * 1 한 것을 더해주고

10의 자리는 10의 자리수 * 10 한 것을 더해주고

100의 자리는 100의 자리수 * 100 한 것을 더해준다.

그러면 A는 100, B는 110이 나온다. 나머지 알파벳은 0이다.

이것을 내림차순으로 정렬하면 110, 100이다.

9부터 차례로 내려가면서 곱해주면 110 * 9 + 100 * 8 = 1790이 된다.

뭐가 A고 뭐가 B인지는 신경쓸 필요 없이 가장 큰 수부터 9와 곱하고 그 다음 큰 수와 8을 곱하고, ... 이런 식으로 하면 된다.

 

입력이 다음과 같이 들어오면

3
ABC
BAC
CCC

A, B, C가 뭐가 될지는 모르겠지만 110A + 110B + 113C를 한 것이 세 숫자의 합이다.

이 110A+110B+113C를 가장 크게 만드는 A, B, C를 찾기만 하면 된다.

그런데 뻔하지 않나? 113이 가장 크므로 C가 9가 되고 A, B가 8, 7이면 된다.

이것을 코드로 구현하기만 하면 된다.

 

코드대로 설명하자면 이차원 벡터 alphabetCount는 다음과 같을 것이다.

alphabet[i][j]의 의미는 빨간색 글씨와 같다.

이제 alphabetCount를 이용하여 tempSum을 채운다.

110, 110, 113을 tempSum에 저장해준다.

그 후 tempSum을 오름차순 정렬하면 다음과 같을 것이다.

num은 9부터 시작해서 1씩 감소하면서 tempSum의 뒤의 원소부터 곱해준다.

113 * 9 + 110 * 8 + 110 * 7 = 2667

2667이 정답이 된다.

 

또 다른 예제를 보자.

입력으로

2
GCF
ACDEB

이렇게 들어온다면

alphabetCount는 다음과 같을 것이다.

이렇게 10000, 1, 1010, 100, 10, 1, 100을 tempSum에 저장해준다.

tempSum 벡터를 오름차순으로 정렬하면

위와 같을 것이다.

이제 num을 9부터 1씩 줄여가면서 tempSum의 뒤의 원소부터 차례로 곱해나가면 된다.

10000 * 9 + 1010 * 8 + 100 * 7 + 100 * 6 + 10 * 5 +1 * 4 + 1 * 3 = 99437

정답은 99437이다.

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<vector<int>> alphabetCount(8, vector<int>(26, 0));
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = s.size() - 1; j >= 0; j--) {
			alphabetCount[s.size() - 1 - j][s[j] - 'A']++;
		}
	}
	vector<int> tempSum(26, 0);
	for (int j = 0; j < 26; j++) {
		for (int i = 0; i < 8; i++) {
			if (alphabetCount[i][j] != 0) {
				tempSum[j] += pow(10, i) * alphabetCount[i][j];
			}
		}
	}
	sort(tempSum.begin(), tempSum.end());
	int num = 9;
	int total = 0;
	for (int i = tempSum.size() - 1; i >= 0; i--) {
		if (tempSum[i] == 0)
			break;
		total += tempSum[i] * num;
		num--;
	}
	cout << total;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2458번 키 순서  (0) 2021.01.19
[백준] 16234번 인구 이동  (0) 2021.01.18
[백준] 5014번 스타트링크  (0) 2021.01.18
[백준] 12100번 2048 (Easy)  (0) 2021.01.18
[백준] 1915번 가장 큰 정사각형  (0) 2021.01.17
728x90

www.acmicpc.net/problem/5014

 

5014번: 스타트링크

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

www.acmicpc.net

최솟값이나 최단시간이 나오면 항상 BFS부터 의심해보자.

버튼을 최소횟수만 눌러서 g층까지 가는 것이므로 BFS로 풀면 된다.

해당 층에 방문한 적이 있다면 다시 방문할 필요가 없다.

BFS는 처음에 방문했을 때가 반드시 최단시간이라는 것이 보장되어 있기 때문이다.

그리고 최고층인 f층보다 높이 갈 수 없고 최저층인 1층보다 낮게 갈 수 없으므로 현재 층 + u가 f보다 크거나 현재층 - d가 1보다 작으면 큐에 넣어주지 않는다.

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int f, s, g, u, d;
	cin >> f >> s >> g >> u >> d;
	vector<bool> visited(f + 1, false);
	queue<pair<int, int>> q; // 현재 층, 현재까지 누른 버튼의 횟수
	q.push(make_pair(s, 0));
	int answer = -1;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		if (cur.first == g) {
			answer = cur.second;
			break;
		}
		if (!visited[cur.first]) {
			visited[cur.first] = true;
			if (cur.first + u <= f) {
				q.push(make_pair(cur.first + u, cur.second + 1));
			}
			if (cur.first - d >= 1) {
				q.push(make_pair(cur.first - d, cur.second + 1));
			}
		}
	}
	if (answer == -1) {
		cout << "use the stairs";
	}
	else {
		cout << answer;
	}
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 16234번 인구 이동  (0) 2021.01.18
[백준] 1339번 단어 수학  (0) 2021.01.18
[백준] 12100번 2048 (Easy)  (0) 2021.01.18
[백준] 1915번 가장 큰 정사각형  (0) 2021.01.17
[백준] 14226번 이모티콘  (0) 2021.01.17
728x90

www.acmicpc.net/problem/12100

 

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

BFS든 DFS든으로 풀 수 있다. 그런데 DFS로 푸는 것이 메모리를 더 절약할 수 있다.

한 쪽으로 미는 동작만 꼼꼼히 잘 구현하면 어려울 것은 없다. 

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<vector<int>> v(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	int maxNum = 0;
	stack<pair<vector<vector<int>>, int>> s;
	s.push(make_pair(v, 0));
	while (!s.empty()) {
		pair<vector<vector<int>>, int> cur = s.top();
		s.pop();
		vector<vector<int>> status = cur.first;
		int cnt = cur.second;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (status[i][j] > maxNum) {
					maxNum = status[i][j];
				}
			}
		}
		if (cnt < 5) {
			// 위
			vector<vector<int>> temp1 = status;
			for (int j = 0; j < n; j++) {
				vector<int> temp;
				for (int i = 0; i < n; i++) {
					if (temp1[i][j] != 0) {
						temp.push_back(temp1[i][j]);
					}
				}
				int index = 0;
				while (true) {
					if (index >= temp.size())
						break;
					if (index + 1 < temp.size()) {
						if (temp[index] == temp[index + 1]) {
							temp[index] *= 2;
							temp.erase(temp.begin() + index + 1);
						}
					}
					index++;
				}
				for (int i = 0; i < temp.size(); i++) {
					temp1[i][j] = temp[i];
				}
				for (int i = temp.size(); i < n; i++) {
					temp1[i][j] = 0;
				}
			}
			s.push(make_pair(temp1, cnt + 1));
			// 왼쪽
			vector<vector<int>> temp2 = status;
			for (int i = 0; i < n; i++) {
				vector<int> temp;
				for (int j = 0; j < n; j++) {
					if (temp2[i][j] != 0) {
						temp.push_back(temp2[i][j]);
					}
				}
				int index = 0;
				while (true) {
					if (index >= temp.size())
						break;
					if (index + 1 < temp.size()) {
						if (temp[index] == temp[index + 1]) {
							temp[index] *= 2;
							temp.erase(temp.begin() + index + 1);
						}
					}
					index++;
				}
				for (int j = 0; j < temp.size(); j++) {
					temp2[i][j] = temp[j];
				}
				for (int j = temp.size(); j < n; j++) {
					temp2[i][j] = 0;
				}
			}
			s.push(make_pair(temp2, cnt + 1));
			// 아래
			vector<vector<int>> temp3 = status;
			for (int j = 0; j < n; j++) {
				vector<int> temp;
				for (int i = n - 1; i >= 0; i--) {
					if (temp3[i][j] != 0) {
						temp.push_back(temp3[i][j]);
					}
				}
				int index = 0;
				while (true) {
					if (index >= temp.size())
						break;
					if (index + 1 < temp.size()) {
						if (temp[index] == temp[index + 1]) {
							temp[index] *= 2;
							temp.erase(temp.begin() + index + 1);
						}
					}
					index++;
				}
				for (int i = 0; i < temp.size(); i++) {
					temp3[n - 1 - i][j] = temp[i];
				}
				for (int i = n - 1 - temp.size(); i >= 0; i--) {
					temp3[i][j] = 0;
				}
			}
			s.push(make_pair(temp3, cnt + 1));
			// 오른쪽
			vector<vector<int>> temp4 = status;
			for (int i = 0; i < n; i++) {
				vector<int> temp;
				for (int j = n - 1; j >= 0; j--) {
					if (temp4[i][j] != 0) {
						temp.push_back(temp4[i][j]);
					}
				}
				int index = 0;
				while (true) {
					if (index >= temp.size())
						break;
					if (index + 1 < temp.size()) {
						if (temp[index] == temp[index + 1]) {
							temp[index] *= 2;
							temp.erase(temp.begin() + index + 1);
						}
					}
					index++;
				}
				for (int j = 0; j < temp.size(); j++) {
					temp4[i][n - 1 - j] = temp[j];
				}
				for (int j = n - 1 - temp.size(); j >= 0; j--) {
					temp4[i][j] = 0;
				}
			}
			s.push(make_pair(temp4, cnt + 1));

		}
	}
	cout << maxNum;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 1339번 단어 수학  (0) 2021.01.18
[백준] 5014번 스타트링크  (0) 2021.01.18
[백준] 1915번 가장 큰 정사각형  (0) 2021.01.17
[백준] 14226번 이모티콘  (0) 2021.01.17
[백준] 1963번 소수 경로  (0) 2021.01.15
728x90

www.acmicpc.net/problem/1915

 

1915번: 가장 큰 정사각형

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

www.acmicpc.net

당연히 브루트포스로 하면 시간초과가 날 것이므로 DP로 접근하였다.

char 타입의 벡터 v에 입력을 받고 벡터 dp를 선언하여 정답을 구했다.

벡터 v와 벡터 dp의 크기는 n행 m열로 선언한 것이 아니라 다음과 같이 n+1행 m+1열로 선언했다. (n = 4, m = 4일 때)

그 이유는 dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j] 이런 식으로 현재 인덱스 - 1을 해줄 때 i - 1 >= 0인지, j - 1 >= 0인지  조건을 체크해줄 필요가 없어서 편하기 때문이다.

dp[i][j]에는 i행 j열을 오른쪽 아래 꼭짓점으로 하는 정사각형의 변의 길이를 저장해주었다.

v[i][j]가 0이면 1로 된 정사각형을 만들 수 없으므로 v[i][j]가 0이면 dp[i][j]는 반드시 0이다.

점화식은

dp[i][j] = min(dp[i - 1][j - 1],  dp[i - 1][j],  dp[i][j - 1]) + 1

이다.

점화식이 왜 이렇게 되는지는 다음 예시를 보면 이해가 갈 것이다.

 

예를 들어 입력으로

3 4
0110
1110
1110

이렇게 들어온다면

벡터 v는 다음과 같을 것이다.

여기서 한 변의 길이가 2인 정사각형을 만들 수 있다.

빨간색 정사각형과 파란색 정사각형을 만들 수 있으므로 dp[2][3] = 2, dp[3][2] = 2가 된다.

그렇다면 dp[3][3]은 몇일까?

만약에 점화식이 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1 이라면 dp[3][3]은 min(2, 2) + 1이므로 3이 된다.

과연 한 변의 길이가 3인 정사각형을 만들 수 있을까?

v[1][1]이 0이므로 변의 길이가 3인 정사각형은 만들 수 없다. 따라서 dp[3][3]은 3이 될 수 없다. v[2][2]가 1이기 때문이다.

dp[3][3]은 2가 되어야 한다.

dp[2][2], dp[2][3], dp[3][2] 중 최솟값에 1을 더한 것이 dp[3][3]의 값 된다.

따라서 점화식은

dp[i][j] = min(dp[i - 1][j - 1],  dp[i - 1][j],  dp[i][j - 1]) + 1

가 된다.

 

예제와 같이 입력이 다음과 같이 들어온다면

4 4
0100
0111
1110
0010

초기 상태의 v와 dp는 다음과 같다.

 

i = 1, j = 1일 때는 v[1][1]이 0이므로 dp[1][1]도 0이다.

 

i = 1, j = 2일 때는 dp[0][0], dp[0][1], dp[1][0]의 최솟값이 0이므로

dp[1][2] = min(dp[0][0], dp[0][1], dp[1][0]) = 0 + 1 = 1이 된다.

 

i = 1, j = 3일 때는 v[1][3]이 0이므로 dp[1][3]도 0이다.

 

i = 1, j = 4일 때는 v[1][4]이 0이므로 dp[1][4]도 0이다.

 

i = 2, j = 1일 때는 v[2][1]이 0이므로 dp[2][1]도 0이다.

 

i = 2, j = 2일 때dp[1][1], dp[1][2], dp[2][1]의 최솟값이 0이므로

dp[2][2] = min(dp[1][1], dp[1][2], dp[2][1]) = min(0, 1, 0) + 1 = 0 + 1 = 1이 된다.

 

i = 2, j = 3일 때는 dp[1][2], dp[1][3], dp[2][2]의 최솟값이 0이므로

dp[2][3] = min(dp[1][2], dp[1][3], dp[2][2]) = min(1, 0, 1) + 1 = 0 + 1 = 1이 된다.

 

i = 2, j = 4일 때는 dp[1][3], dp[1][4], dp[2][3]의 최솟값이 0이므로

dp[2][4] = min(dp[1][3], dp[1][4], dp[2][3]) = min(0, 0, 1) + 1 = 0 + 1 = 1이 된다.

 

i = 3, j = 1일 때dp[2][0], dp[2][1], dp[3][0]의 최솟값이 0이므로

dp[3][1] = min(dp[2][0], dp[2][1], dp[3][0]) = min(0, 0, 0) + 1 = 0 + 1 = 1이 된다.

 

i = 3, j = 2일 때는 dp[2][1], dp[2][2], dp[3][1]의 최솟값이 0이므로

dp[3][2] = min(dp[2][1], dp[2][2], dp[3][1]) = min(0, 1, 1) + 1 = 0 + 1 = 1이 된다.

 

i = 3, j = 3일 때는 dp[2][2], dp[2][3], dp[3][2]의 최솟값이 1이므로

dp[3][3] = min(dp[2][2], dp[2][3], dp[3][2]) = min(1, 1, 1) + 1 = 1 + 1 = 2가 된다.

 

i = 3, j = 4일 때는 v[3][4]이 0이므로 dp[3][4]도 0이다.

 

i = 4, j = 1일 때는 v[4][1]이 0이므로 dp[4][1]도 0이다.

 

i = 4, j = 2일 때는 v[4][2]이 0이므로 dp[4][2]도 0이다.

 

i = 4, j = 3일 때는 dp[3][2], dp[3][3], dp[4][2]의 최솟값이 0이므로

dp[4][3] = min(dp[2][2], dp[2][3], dp[3][2]) = min(1, 2, 0) + 1 = 0 + 1 = 1이 된다.

 

i = 4, j = 4일 때는 v[4][4]이 0이므로 dp[4][4]도 0이다.

 

이렇게 dp를 완성했으면 dp를 돌면서 최댓값을 찾으면 그것이 1로 만들 수 있는 가장 큰 정사각형의 한 변의 길이이다.

우리가 출력해야 하는 것은 가장 큰 정사각형의 넓이이므로 한 변의 길이의 제곱을 하면 된다.

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<vector<char>> v(n + 1, vector<char>(m + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> v[i][j];
		}
	}
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (v[i][j] == '1') {
					dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
				
			}
			else {
				dp[i][j] = 0;
			}
		}
	}
	int maxLength = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (dp[i][j] > maxLength) {
				maxLength = dp[i][j];
			}
		}
	}
	cout << maxLength * maxLength;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 5014번 스타트링크  (0) 2021.01.18
[백준] 12100번 2048 (Easy)  (0) 2021.01.18
[백준] 14226번 이모티콘  (0) 2021.01.17
[백준] 1963번 소수 경로  (0) 2021.01.15
[백준] 11725번 트리의 부모 찾기  (0) 2021.01.14
728x90

www.acmicpc.net/problem/14226

 

14226번: 이모티콘

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만

www.acmicpc.net

처음에는 BFS인지 DP인지 헷갈려서 DP로 접근했다가 틀리고 BFS로 풀었다.

최단시간에 이모티콘을 만들어야 하므로 DFS가 아니라 BFS로 풀어야 한다. 최단경로, 최단시간 이런 것을 구해야하는 문제라면 BFS를 의심해보자.

이 문제에서는 저 visited를 체크하는 것이 관건인 것 같다.

나는 visited를 map에 저장해주었다.

visited[(5, 3)]은 화면에 이모티콘에 5개가 있고 클립보드에 이모티콘이 3개 있는 상태에 도달한 적이 있는지 없는지를 저장한다.

한 번 방문했으면 다시 방문할 필요가 없는 이유가 BFS이기 때문에 그 이후에 방문하면 걸린 시간이 무조건 더 많이 걸리기 때문이다. 최단시간이 걸리는 경우를 구해야 하므로 한 번 방문했으면 다시 방문할 필요가 없다.

큐에 들어가는 원소는

(화면에 있는 이모티콘 개수, 클립보드에 저장된 이모티콘 개수, 지금 상태까지 몇 초가 걸렸는지)

이렇게 생긴 튜플이다.

큐에 넣을 때는 튜플의 3번째 원소는 무조건 1을 증가한다. 연산 하나에 1초가 걸리기 때문이다.

#include <iostream>
#include <queue>
#include <tuple>
#include <map>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	queue<tuple<int, int, int>> q; // 화면에 있는 이모티콘 개수, 클립보드에 있는 이모티콘 개수, 몇 초 걸렸는지
	q.push(make_tuple(1, 0, 0));
	map<pair<int, int>, bool> visited;
	while (!q.empty()) {
		tuple<int, int, int> cur = q.front();
		int emoticonNum = get<0>(cur);
		int clipboardNum = get<1>(cur);
		int seconds = get<2>(cur);
		q.pop();
		if (emoticonNum == n) {
			cout << seconds;
			break;
		}
		if (!visited[make_pair(emoticonNum, clipboardNum)]) {
			visited[make_pair(emoticonNum, clipboardNum)] = true;
			if (get<1>(cur) > 0) { // 클립보드가 비어있지 않으면 화면에 붙여넣기
				q.push(make_tuple(emoticonNum + clipboardNum, clipboardNum, seconds + 1));
			}
			if (get<0>(cur) > 1) { // 화면에 있는 이모티콘 개수가 2 이상이면 화면에 있는 이모티콘 하나 삭제
				q.push(make_tuple(emoticonNum - 1, clipboardNum, seconds + 1));
			}
			q.push(make_tuple(emoticonNum, emoticonNum, seconds + 1)); //현재 화면의 상태를 클립보드에 저장
		}
	}
	return 0;
}
728x90

+ Recent posts