거의 2달만에 푸는 백준이다. 컴퓨터 환경 세팅을 오랫동안 하고(...) 간단히 워밍업 느낌으로 안 푼 문제 중 쉬운 문제들 몇 개만 풀어보았다.
백준 14502번: 연구소
처음에 보고 당황했는데, 다행히 n이 작았다. 모든 조합을 다 해보면서 DFS/BFS를 돌리면 간단하게 풀 수 있다.
만약 n이 크다면? 유량으로 풀어야 할 것 같은데 정확히 모르겠다.
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
int n, m, cnt, ans;
int map[8][8], temp[8][8];
int loc[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<ii> two;
void dfs(int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= m) return;
if (temp[i][j] != 0) return;
temp[i][j] = 2;
cnt++;
for (int k = 0; k < 4; ++k) {
dfs(i + loc[k][0], j + loc[k][1]);
}
}
void copy() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
temp[i][j] = map[i][j];
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
vector<ii> zero;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> map[i][j];
if (map[i][j] == 0) zero.push_back(ii(i, j));
else if (map[i][j] == 2) {
two.push_back(ii(i, j));
map[i][j] = 0;
}
}
}
int z = zero.size();
for (int i = 0; i < z; ++i) {
for (int j = i + 1; j < z; ++j) {
for (int k = j + 1; k < z; ++k) {
copy();
temp[zero[i].first][zero[i].second] = 1;
temp[zero[j].first][zero[j].second] = 1;
temp[zero[k].first][zero[k].second] = 1;
cnt = -two.size();
for (ii u: two) {
dfs(u.first, u.second);
}
ans = max(ans, z - cnt - 3);
}
}
}
cout << ans;
}
백준 1735번: 분수 합
gcd 짜기가 귀찮으면 #include <algorithm>을 한 뒤 __gcd를 쓰면 된다.
범위가 3만까지인데, 초심자용으로 아주 좋은 범위라고 생각한다.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a, b, c, d, e, f;
cin >> a >> b >> c >> d;
e = a * d + b * c, f = b * d;
cout << e / __gcd(e, f) << ' ' << f / __gcd(e, f);
}
배열의 크기를 100으로 잡아서 (약간 침범해도 상관없을 줄 알았는데 아니었던 것 같다) 틀렸다.
왜 그런지 몰라서 한참 찾았다. 배열을 넉넉히 잡는 습관을 들이자.
#include <iostream>
#include <memory.h>
using namespace std;
int n;
char map[101][101];
int loc[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool vis[101][101];
void dfs(int i, int j, bool cb) {
vis[i][j] = 1;
for (int k = 0; k < 4; ++k) {
int x, y;
x = i + loc[k][0];
y = j + loc[k][1];
if (x < 0 || x >= n || y < 0 || y >= n) continue;
if (vis[x][y]) continue;
if (cb) {
if (map[x][y] == map[i][j] || map[x][y] + map[i][j] == 'R' + 'G') dfs(x, y, cb);
}
else if (map[x][y] == map[i][j]) dfs(x, y, cb);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) cin >> map[i];
int ncb = 0, cb = 0;
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
if (!vis[i][j]) {
dfs(i, j, 0);
ncb++;
}
}
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
if (!vis[i][j]) {
dfs(i, j, 1);
cb++;
}
}
cout << ncb << ' ' << cb;
}
백준 14888번: 연산자 끼워넣기
n이 작으므로 그냥 다 해보는 문제. next_permutation을 쓰면 코드가 간단해질 것이니 참고.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, t;
cin >> n;
vector<int> arr(n), op;
for (int i = 0; i < n; ++i) cin >> arr[i];
for (int i = 0; i < 4; ++i) {
cin >> t;
while (t--) op.push_back(i);
}
int mina = 1e9 + 10, maxa = -1e9 - 10;
do {
int loc = arr[0];
for (int i = 1; i < n; ++i) {
if (op[i - 1] == 0) loc += arr[i];
else if (op[i - 1] == 1) loc -= arr[i];
else if (op[i - 1] == 2) loc *= arr[i];
else if (op[i - 1] == 3) loc /= arr[i];
}
mina = min(mina, loc);
maxa = max(maxa, loc);
} while (next_permutation(op.begin(), op.end()));
cout << maxa << '\n' << mina;
}
