개발/알고리즘
21년 8월 알고리즘 스터디 3주차
라사 RASA
2022. 7. 2. 18:51
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';
}