21년 8월 알고리즘 스터디 3주차

5430번 : AC

---

    맨 앞자리를 간단하게 버리기 위해 deque 를 사용하여 해결했다. 1차 시도 때는 말 그대로 구현했고, 시간 초과가 나와서 그 다음으로는 R 이 연속으로 짝수 번 있으면 무시하고 넘어가도록 처리했다. 하지만 여전히 시간 초과가 나와서 고민해보니 R 명령의 경우 D 만 잘 처리해주면 마지막에 처리해도 상관 없는 것 같아서 Reverse 여부를 확인하는 isReverse 변수를 만들어서 처리했다.

 

#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

int T, n;
bool isError, isReverse;
string p, input, trans;
deque <int> seq;

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

	cin >> T;

	while (T--)
	{
		isError = isReverse = false;

		cin >> p >> n >> input;

		seq.clear();
		trans = "";

		input = input.substr(1, input.size() - 2);

		for (int i = 0; i < input.size(); ++i)
		{
			if (input.substr(i,1).compare(","))
				trans += input[i];

			else
			{
				if(trans.compare(""))
					seq.push_back(stoi(trans));
				trans = "";
			}
		}

		if(trans.compare(""))
			seq.push_back(stoi(trans));

		for (int i = 0; i < p.size(); ++i)
		{
			if (p[i] == 'R')
			{
				isReverse = !isReverse;
			}

			else if (p[i] == 'D')
			{
				if (seq.empty())
				{
					isError = true;
					break;
				}

				if (isReverse)
					seq.pop_back();

				else
					seq.pop_front();
			}
		}

		if (isError)
			cout << "error\n";
		
		else
		{
			cout << '[';

			while (!seq.empty())
			{
				if (isReverse)
				{
					cout << seq[seq.size() - 1];
					seq.pop_back();
				}

				else
				{
					cout << seq[0];
					seq.pop_front();
				}
				
				if (seq.size())
					cout << ',';
			}

			cout << "]\n";
		}
	}
}

 

 

1041번 : 주사위

---

    "A B C D E F" 에서 (A, F), (B, E), (C, D) 가 서로 반대되는 면이어서, 반복문 내에 i 와 5-i 를 이용해서 처리했다. 예제에서 N 이 1,000,000 일 때 int 형 범위를 넘어가서 long long 을 이용하여 처리했다. 처음에는 ans 에만 long long 형을 사용했는데, 계속 오버플로우가 나서 찾아보니 long long 형 변수와 int 형 변수를 사칙 연산하면 int 형 결과가 나와서 생기는 문제였다. 나머지 변수도 long long 으로 바꿔서 해결했다.

 

#include <iostream>

using namespace std;

int main(void)
{
	long long side[6];
	long long N, ans, min_side, min_edge, min_vertex, max;

	min_side = min_edge = min_vertex = 151;

	cin >> N;

	ans = 0;
	max = 0;

	for (int i = 0; i < 6; ++i)
	{
		cin >> side[i];
		min_side = (min_side < side[i]) ? min_side : side[i];
		
		max = (max > side[i]) ? max : side[i];
		ans += side[i];
	}

	for (int i = 0; i < 6; ++i)
	{
		for (int j = 0; j < 6; ++j)
		{
			if (j == i || j == 5 - i)
				continue;
            
            min_edge = (min_edge < side[i] + side[j]) ? min_edge : side[i] + side[j];

			for (int k = 0; k < 6; ++k)
			{
				if (k == i || k == j || k == 5 - i || k == 5 - j)
					continue;

				min_vertex = (min_vertex < side[i] + side[j] + side[k]) ? min_vertex : side[i] + side[j] + side[k];

			}
		}
	}

	if (N > 1)
		ans = (5 * N * N - 16 * N + 12) * min_side + (8 * N - 12) * min_edge + 4 * min_vertex;
    
	else
		ans -= max;

	cout << ans << '\n';
}

 

 

1793 번 : 타일링

---

    long long 형을 넘어가는 값이 답이 나오는 경우만 잘 처리하면 간단한 문제였다. dp 에 2x1 타일을 사용하는 경우, 2x2 타일을 사용하는 경우를 계산해 방법의 수를 역순으로 저장하고, 마지막으로 10 이상이면 자릿수를 높여주는 법으로 해결했다.

 

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int N;
vector<deque<int>> cache;

deque<int> dp(int pos)
{
	if (pos == N)
		return deque<int>(1,1);

	if (pos > N)
		return deque<int>(1,0);

	if (cache[pos].size() != 0)
		return cache[pos]; 

	deque<int> jump1, jump2;

	int max_size, digit, i, tmp;

	jump2 = dp(pos + 2);
	jump1 = dp(pos + 1);

	max_size = (jump1.size() > jump2.size()) ? jump1.size() : jump2.size();

	for (i = max_size - 1; i >= 0; --i)
	{
		if (i < jump1.size() && i < jump2.size())
		{
			digit = jump1[i] + 2 * jump2[i];
		}

		else if (i < jump1.size())
		{
			digit = jump1[i];
		}

		else
		{
			digit = 2 * jump2[i];
		}

		cache[pos].push_front(digit);
	}

	i = 0;

	while (i < cache[pos].size())
	{
		if (cache[pos][i] > 9)
		{
			if (i != cache[pos].size() - 1)
				cache[pos][i + 1] += cache[pos][i] / 10;

			else
				cache[pos].push_back(cache[pos][i] / 10);

			cache[pos][i] %= 10;
		}

		++i;
	}

	return cache[pos];
}

int main(void)
{
	while (cin >> N)
	{
		cache.assign(N + 1, deque<int>());

		cache[0] = dp(0);

		for (int i = cache[0].size() - 1; i >= 0; --i)
			cout << cache[0][i];
		cout << '\n';
	}
}

 

 

10819 번 : 차이를 최대로

---

    sort 한 뒤, next_permutation 로 모든 경우의 차이를 확인하는 방식으로 구현했다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, ans, temp;
vector<int> A;

int main(void)
{
	ans = -1;
	cin >> N;

	A.assign(N, 0);

	for (int i = 0; i < N; ++i)
		cin >> A[i];

	sort(A.begin(), A.end());
    
	while (ans == -1 || next_permutation(A.begin(), A.end()))
	{
		temp = 0;

		for (int i = 0; i < A.size() - 1; ++i)
			temp += abs(A[i] - A[i + 1]);

		ans = max(ans, temp);
	}

	cout << ans << '\n';
}

 

 

1926 번 : 그림

---

    DFS 를 몇 번 호출해야 되는지 계산해서 그림의 개수를 파악했고, dfs 함수에서 탐색 횟수를 반환하게 구현해서 그림의 넓이를 구했다.

 

#include <iostream>
#include <vector>

using namespace std;

int n, m, ans, temp, cnt;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

vector<vector<int>> paper;
vector<vector<bool>> visited;

int dfs(int x, int y)
{
	int size = 0;

	visited[x][y] = true;

	for (int k = 0; k < 4; ++k)
	{
		if (x + dx[k] >= n || x + dx[k] < 0 || y + dy[k] >= m || y + dy[k] < 0)
			continue;

		if (paper[x + dx[k]][y + dy[k]] == 1 && !visited[x + dx[k]][y + dy[k]])
		{
			size += dfs(x + dx[k], y + dy[k]);
		}
	}

	return 1 + size;
}

int main(void)
{
	ans = cnt = 0;
	cin >> n >> m;

	paper.assign(n, vector<int>(m, 0));
	visited.assign(n, vector<bool>(m, false));

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> paper[i][j];
		}
	}

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			temp = 0;

			if (paper[i][j] == 1 && !visited[i][j])
			{
				temp = dfs(i, j);
				++cnt;
			}

			ans = (ans > temp) ? ans : temp;
		}
	}

	cout << cnt << '\n' << ans << '\n';
}

 

 

2251 번 : 물통

---

    각 컵에 번호를 부여해서 BFS 로 옮길 수 있는 모든 경우를 확인했다. 문제를 다 풀고 다른 이의 풀이를 확인하며 visited 를 2 차원까지만 써도 된다는 걸 확인했다. 풀이를 보며 신경써야하는 것과 신경쓰지 않아도 되는 것을 확실히 파악하는게 중요하다고 생각했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

int vol[3], current[3];
vector<int> ans;
queue<tuple<int, int, int>> q;
int visited[201][201][201] = { false, };

void move_water(int origin, int target, int none)
{
	// 합친 물의 양
	int check_size = current[origin] + current[target];
	int check[3];

	// 옮긴 후 각 컵에 담긴 물의 양
	check[origin] = 0;
	check[target] = check_size;
	check[none] = current[none];

	if (check_size <= vol[target] && !visited[check[0]][check[1]][check[2]])
	{
		q.push({ check[0],check[1],check[2] });
		visited[check[0]][check[1]][check[2]] = true;
	}

	check[origin] = check_size - vol[target];
	check[target] = vol[target];

	if (check_size > vol[target] && !visited[check[0]][check[1]][check[2]])
	{
		q.push({ check[0],check[1],check[2] });
		visited[check[0]][check[1]][check[2]] = true;
	}
}

int main(void)
{
	cin >> vol[0] >> vol[1] >> vol[2];

	visited[0][0][vol[2]] = true;
	ans.push_back(vol[2]);

	q.push({ 0, 0, vol[2] });

	while (!q.empty())
	{
		tie(current[0], current[1], current[2]) = q.front();
		q.pop();

		if (current[0] == 0)
			ans.push_back(current[2]);

		move_water(0, 1, 2);
		move_water(0, 2, 1);
		move_water(1, 0, 2);
		move_water(1, 2, 0);
		move_water(2, 0, 1);
		move_water(2, 1, 0);
	}

	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());

	for (int i = 0; i < ans.size(); ++i)
		cout << ans[i] << ' ';
	cout << '\n';

}