오랜만에 백준을 풀어보았다. 감이 좀 떨어진 것이 느껴진다.
오랜만에 codeforces도 해보았다. Div3이었는데도 참교육당했다.
백준 17144번: 미세먼지 안녕!
정직한 구현 문제. 미세먼지는 상하좌우 4방향으로 확산이 일어나고, 공기청정기 바람의 경로에 있는 먼지들은 바람의 방향대로 한 칸씩 이동한다.
공기청정기 바람의 방향 때문에 조금 노가다가 심하다. 더 짧게 짤 수는 있겠지만 빨리 짜는 것과 적당히 밸런스를 맞추어야 한다.
코드 보기 접기
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int r, c, t;
cin >> r >> c >> t;
int air[51][51] = {};
int pos1 = -1, pos2 = -1;
for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) {
cin >> air[i][j];
if (air[i][j] == -1) {
if (pos1 == -1) pos1 = i;
else pos2 = i;
}
}
for (int rep = 0; rep < t; ++rep) {
int temp[51][51] = {};
for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) {
if (air[i][j] == -1) {
temp[i][j] = -1;
continue;
}
int pol = air[i][j] / 5;
if (i != 0 && air[i - 1][j] != -1) {
temp[i - 1][j] += pol;
air[i][j] -= pol;
}
if (i != r - 1 && air[i + 1][j] != -1) {
temp[i + 1][j] += pol;
air[i][j] -= pol;
}
if (j != 0 && air[i][j - 1] != -1) {
temp[i][j - 1] += pol;
air[i][j] -= pol;
}
if (j != c - 1 && air[i][j + 1] != -1) {
temp[i][j + 1] += pol;
air[i][j] -= pol;
}
temp[i][j] += air[i][j];
}
int tt1 = 0, tt2 = 0;
for (int i = pos1 - 1; i >= 1; --i) temp[i][0] = temp[i - 1][0];
for (int i = pos2 + 1; i < r - 1; ++i) temp[i][0] = temp[i + 1][0];
for (int i = 0; i < c - 1; ++i) {
temp[0][i] = temp[0][i + 1];
temp[r - 1][i] = temp[r - 1][i + 1];
}
for (int i = 0; i < pos1; ++i) temp[i][c - 1] = temp[i + 1][c - 1];
for (int i = r - 1; i > pos2; --i) temp[i][c - 1] = temp[i - 1][c - 1];
for (int i = c - 1; i >= 2; --i) {
temp[pos1][i] = temp[pos1][i - 1];
temp[pos2][i] = temp[pos2][i - 1];
}
temp[pos1][1] = 0;
temp[pos2][1] = 0;
for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) air[i][j] = temp[i][j];
}
int ans = 0;
for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) {
if (air[i][j] != -1) ans += air[i][j];
}
cout << ans;
}
접기
백준 16496번: 큰 수 만들기
주어진 숫자들을 이어붙여서 가장 큰 수를 만들어야 한다. 그냥 사전순으로 큰 수부터 이어붙이면 크겠다.
문제는 한 수가 다른 수에 포함되는 경우(예를 들어 32482, 324), 동일한 구간 뒤에 오는 숫자가 무엇인지 고려해주어야 한다.
이걸 어떻게 비교할까? 유심히 생각을 하다보면 한 가지 특징을 발견할 수 있다.
다음의 4가지 숫자가 있다고 가정해보자.
324|82
324|
122
20
사전순으로 가장 빠른 것을 찾다보면 324까지는 동일하며, 두 가지 후보가 생기게 된다.
32472는 82가 뒤에 오지만 324는?
324 뒤에는, 지금까지 사전 순으로 가장 컸던 324~ 가 또 와야만 한다.
즉, 반복을 할 때 324324324...의 순으로 채워가며 비교하면 되는 것이다.
나는 가장 긴 수를 기준으로 뒤를 다 채워놓고 정렬해주었지만 정렬의 comp함수를 재정의하면 훨씬 깔끔한 코드가 나온다.
comp함수를 쓸 때 매개변수에 &를 붙여주어야 하던가.. 잘 기억이 안 난다.
코드 보기 접기
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool comp(string& a, string& b) {
int n = max(a.size(), b.size());
for (int i = 0; i < n; ++i) {
if (a[i % a.size()] != b[i % b.size()]) return a[i % a.size()] < b[i % b.size()];
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<string> arr(n);
for (int i = 0; i < n; ++i) cin >> arr[i];
sort(arr.begin(), arr.end(), comp);
if (arr[n - 1] == "0") cout << 0;
else {
for (int i = n - 1; i >= 0; --i) cout << arr[i];
}
}
접기
백준 1655번: 가운데를 말해요
숫자들이 차례로 들어올 때 중간값을 출력해야 하는 문제이다.
유명한 방법이 있는데, 최소 힙과 최대 힙 두가지를 이용하는 방법이다.
최대 힙에는 작은 절반의 원소를, 최소 힙에는 큰 절반의 원소를 넣는다. 숫자가 하나 들어올 때마다 둘의 갯수를 잘 유지해주면 된다.
코드 보기 접기
#include <iostream>
#include <queue>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, t;
cin >> n;
priority_queue<int> low;
priority_queue<int, vector<int>, greater<int>> high;
low.push(-10010);
high.push(10010);
for (int i = 0; i < n; ++i) {
cin >> t;
if (i & 1) {
if (t > low.top()) high.push(t);
else {
high.push(low.top());
low.pop();
low.push(t);
}
}
else {
if (t < high.top()) low.push(t);
else {
low.push(high.top());
high.pop();
high.push(t);
}
}
cout << low.top() << '\n';
}
}
접기
백준 8989번: 시계
시간 5개가 주어졌을 때, 시계의 각도 순으로 중간 각도 값을 갖는 시간을 출력하는 문제이다.
핵심은 시계의 각도를 구하는 과정이라고 할 수 있다.
다들 알다시피 시침의 각도는 (30 * 시 + 0.5 * 분), 분침의 각도는 (6 * 분)이다.
각도가 주어지면 둘 중 작은 쪽의 각도를 보통 생각하기 때문에 180보다 크면 360 - 각도를 사용해야 한다.
소수가 나오면 오류를 유발하니 2를 곱해 생각하면 편하다.
코드 보기 접기
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tc;
cin >> tc;
while (tc--) {
pair<int, string> angle[5];
for (int i = 0; i < 5; ++i) {
string s;
cin >> s;
int h = (s[0] - '0') * 10 + s[1] - '0';
int m = (s[3] - '0') * 10 + s[4] - '0';
int d = abs(m * 12 - (h * 60 + m));
while (d >= 720) d -= 720;
if (d > 360) d = 720 - d;
angle[i] = pair<int, string>(d, s);
}
sort(angle, angle + 5);
cout << angle[2].second << '\n';
}
}
접기
백준 4677번: Oil Deposits
랜덤으로 풀다 보니 영어 문제가 걸렸다. @는 석유, *는 일반 땅인데 서로 붙어 있는 석유를 한 뭉텅이로 생각했을 때 석유 뭉텅이가 총 몇 개인지 구하는 문제이다.
대각선까지 같은 뭉텅이로 본다는 것이 특징이라면 특징. DFS나 BFS로 가볍게 풀 수 있다.
코드 보기 접기
#include <iostream>
#include <memory.h>
using namespace std;
int m, n;
char map[101][101];
bool vis[101][101];
void dfs(int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n) return;
if (map[x][y] == '*' || vis[x][y]) return;
vis[x][y] = 1;
for (int i = -1; i <= 1; ++i) for (int j = -1; j <= 1; ++j) dfs(x + i, y + j);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
while (cin >> m >> n, m) {
memset(vis, 0, sizeof(vis));
for (int i = 0; i < m; ++i) cin >> map[i];
int cnt = 0;
for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) {
if (map[i][j] == '@' && !vis[i][j]) {
cnt++;
dfs(i, j);
}
}
cout << cnt << '\n';
}
}
접기
백준 1718번: 암호
생략
코드 보기 접기
#include <iostream>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s, key;
getline(cin, s);
cin >> key;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == ' ') cout << ' ';
else {
char c = s[i] - (key[i % key.size()] - 'a' + 1);
if (c < 'a') c += 26;
cout << c;
}
}
}
접기
백준 15917번: 노솔브 방지문제야!!
노솔브 방지문제라길래 호다닥 풀었다. 각 쿼리가 2의 거듭제곱 꼴인지 묻는 문제인데,
https://jeonggyun.tistory.com/208
에서도 쓴 바 있지만 i & (i - 1) == 0으로 가볍게 판별할 수 있다.
코드 보기 접기
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int q, t;
cin >> q;
while (q--) {
cin >> t;
cout << !(t & (t - 1)) << '\n';
}
}
접기
백준 9411번: 실수 계산
실수의 합을 정확하게 계산하는 문제이다.
문제 설명이 약간 애매한데, 유효 숫자가 30자리라서 (0.000...(100만 개)...0001234) 이런 입력도 가능할 것 같아서 긴장했는데, 다행히 없는 것 같다.
+, -를 잘 처리해주고, 자릿수를 잘 맞추어 더해주고, 출력할 때 그냥 정수인지 / 0보다 한참 작은 소수인지 등을 잘 처리해주면 된다.
약간 예외 케이스가 있을 것 같기도 한 코드이다. 설마 없겠지.. ㅎ
코드 보기 접기
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct real {
string before;
string after;
int len1, len2;
char sign = 1;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tc;
cin >> tc;
string s;
while (tc--) {
vector<real> vec;
int ml1 = 0, ml2 = 0;
while (cin >> s, s != "0") {
real t;
if (s[0] == '-') {
t.sign = -1;
s = s.substr(1, s.size() - 1);
}
int a = s.find('.');
if (a == -1) {
t.len1 = s.size();
t.len2 = 0;
t.before = s;
}
else {
t.len1 = s.find('.');
t.len2 = s.size() - t.len1 - 1;
t.before = s.substr(0, t.len1);
t.after = s.substr(t.len1 + 1, t.len2);
}
ml1 = max(ml1, t.len1);
ml2 = max(ml2, t.len2);
vec.push_back(t);
}
vector<int> cal(ml1 + ml2 + 4, 0);
for (real u: vec) {
for (int i = 0; i < u.len1; ++i) {
cal[ml1 + 2 - u.len1 + i] += u.sign * (u.before[i] - '0');
}
for (int i = 0; i < u.len2; ++i) {
cal[ml1 + 2 + i] += u.sign * (u.after[i] - '0');
}
}
for (int i = cal.size() - 1; i >= 1; --i) {
while (cal[i] < 0) {
cal[i] += 10;
cal[i - 1] -= 1;
}
while (cal[i] >= 10) {
cal[i] -= 10;
cal[i - 1] += 1;
}
}
if (cal[0] < 0) {
cout << '-';
for (int i = 0; i < cal.size(); ++i) cal[i] = -cal[i];
for (int i = cal.size() - 1; i >= 1; --i) {
while (cal[i] < 0) {
cal[i] += 10;
cal[i - 1] -= 1;
}
while (cal[i] >= 10) {
cal[i] -= 10;
cal[i - 1] += 1;
}
}
}
int start = -1, end = -1;
for (int i = 0; i < cal.size(); ++i) {
if (start == -1 && cal[i] != 0) {
start = i;
break;
}
}
for (int i = cal.size() - 1; i >= 0; --i) {
if (end == -1 && cal[i] != 0) {
end = i;
break;
}
}
if (start == -1 && end == -1) cout << 0;
else {
if (start > ml1 + 1) {
cout << "0.";
for (int i = 0; i < start - ml1 - 2; ++i) cout << 0;
}
for (int i = start; i <= end; ++i) {
cout << cal[i];
if (i == ml1 + 1 && i != end) cout << '.';
}
if (end < ml1 + 1) {
for (int i = 0; i < ml1 + 1 - end; ++i) cout << 0;
}
}
cout << '\n';
}
}
접기
