백준 BOJ 문제 풀이 기록 220831
백준 BOJ 18017번 : 총알의 속도
문제 난이도 : 난이도를 매길 수 없음
알고리즘 분류 : 물리학
A m/s로 달리며 B m/s로 총알을 발사했을 때 총알의 속력을 구하는 문제이다.
이 때 A, B는 10^8 이하이며, 10^(-9) 이내의 오차로 답을 구해야 한다.
상대성 이론을 사용하는 문제이다.
왜냐하면 속력이 10^8 수준까지 매우 커지면 빛의 속력을 고려할 필요가 있기 때문이다.
따라서 다음의 공식을 사용한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
double a, b; cin >> a >> b;
double c = 299792458;
double ans = (a + b) / (1 + (a * b) / (c * c));
cout << fixed;
cout.precision(9);
cout << ans << "\n";
}
백준 BOJ 3154번 : 알람시계
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
시간을 맞출 때 시는 24로 나눈 나머지로, 분은 60으로 나눈 나머지로 자동으로 맞춰진다고 할 때 번호키 사이의 맨해튼 거리의 합이 가장 작도록 시간을 입력하려면 어떻게 입력해야 하는지 구하는 문제이다.
번호키가 수식 하나로 거리를 나타내기 어려우므로, 일단은 번호와 번호 사이의 거리를 모두 구해주고 00:00부터 99:99까지 중에 조건에 해당하면서 가장 거리의 합이 작은 것을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b; scanf("%02d:%02d", &a, &b);
int v[10][10] = {{0, 4, 3, 4, 3, 2, 3, 2, 1, 2},
{4, 0, 1, 2, 1, 2, 3, 2, 3, 4},
{3, 1, 0, 1, 2, 1, 2, 3, 2, 3},
{4, 2, 1, 0, 3, 2, 1, 4, 3, 2},
{3, 1, 2, 3, 0, 1, 2, 1, 2, 3},
{2, 2, 1, 2, 1, 0, 1, 2, 1, 2},
{3, 3, 2, 1, 2, 1, 0, 3, 2, 1},
{2, 2, 3, 4, 1, 2, 3, 0, 1, 2},
{1, 3, 2, 3, 2, 1, 2, 1, 0, 1},
{2, 4, 3, 2, 3, 2, 1, 2, 1, 0}};
int Min = INT_MAX, x, y;
for(int i=0; i<100; i++)
for(int j=0; j<100; j++) {
if(i % 24 != a || j % 60 != b) continue;
int sum = v[i/10][i%10] + v[i%10][j/10] + v[j/10][j%10];
if(sum < Min) {
Min = sum;
x = i, y = j;
}
}
printf("%02d:%02d\n", x, y);
}
백준 BOJ 5371번 : Annoying Mosquitos
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
N개의 모기의 좌표가 주어지고, M개의 파리채의 중심 좌표가 주어질 때, 파리채는 중심 좌표를 기준으로 가로 세로 ±50만큼의 범위에 있는 모기를 잡을 수 있다고 한다면 잡을 수 있는 모기의 수를 구하는 문제이다.
브루트포스로 각 파리채의 위치에 대해 잡히는 모기들을 bool 변수로 check 해주면 된다.
모든 파리채 검사 이후 최종적으로 check 되어있는 모기들의 수를 구하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
vector<pair<int, int>> v(N);
for(int i=0; i<N; i++)
cin >> v[i].first >> v[i].second;
vector<bool> u(N);
int M; cin >> M;
while(M--) {
int x, y; cin >> x >> y;
for(int i=0; i<N; i++) {
if(v[i].first <= x + 50 && v[i].first >= x - 50
&& v[i].second <= y + 50 && v[i].second >= y - 50) u[i] = true;
}
}
int ans = 0;
for(int i=0; i<N; i++)
if(u[i]) ans++;
cout << ans << "\n";
}
}
백준 BOJ 5768번 : Divide and Conquer
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
주어진 a ~ b 사이의 수 중에서 약수의 개수가 가장 많은 것, 그리고 그러한 수가 여러 개라면 가장 큰 수를 구하고, 그 약수의 개수를 구하는 문제이다.
직접 a ~ b 사이의 모든 수들에 대해 약수의 개수를 구해보면서 그들 중 가장 큰 수를 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int a, b; cin >> a >> b;
if(a == 0 && b == 0) break;
int Max = 0, ans;
for(int i=a; i<=b; i++) {
int cnt = 0;
for(int j=1; j<=i; j++) {
if(i % j == 0) cnt++;
}
if(cnt >= Max) {
Max = cnt;
ans = i;
}
}
cout << ans << " " << Max << "\n";
}
}
백준 BOJ 6367번 : Color Me Less
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
16개의 값들 중 RGB 거리가 가장 가까운 것을 매칭시켜주는 문제이다.
매 테스트케이스마다 16개의 값들에 대한 거리를 직접 구한 뒤 그들 중 가장 작은 것을 직접 찾아주면 된다.
특별히 다른 처리를 하지 않았는데 맞는 것을 보면 RGB 거리가 같은 두 점이 존재하지는 않는 것 같다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
vector<s> v(16);
for(int i=0; i<16; i++)
cin >> v[i].a >> v[i].b >> v[i].c;
while(true) {
int a, b, c; cin >> a >> b >> c;
if(a == -1 && b == -1 && c == -1) break;
int Min = INT_MAX, x, y, z;
for(int i=0; i<16; i++) {
int val = pow(a - v[i].a, 2) + pow(b - v[i].b, 2) + pow(c - v[i].c, 2);
if(val < Min) {
Min = val;
x = v[i].a, y = v[i].b, z = v[i].c;
}
}
cout << "(" << a << "," << b << "," << c << ") maps to ("
<< x << "," << y << "," << z << ")\n";
}
}
백준 BOJ 11321번 : Addition Affliction
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
두 수를 더한 일의 자리가 0이 되는 조합을 먼저 계산하도록 수식의 앞에 배치해주는 문제이다.
앞에서부터 2중 for문을 돌리며 두 수의 합이 10으로 나누어떨어지는 것들을 체크해서 벡터에 push back 해주면 된다.
이미 체크가 된 것은 건너뛰어주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
string str; cin >> str;
if(str == "0") break;
vector<int> v;
string tmp = "";
for(int i=0; i<str.length(); i++) {
if(str[i] != '+') tmp += str[i];
else {
v.push_back(stoi(tmp));
tmp = "";
}
}
v.push_back(stoi(tmp));
tmp = "";
vector<bool> u(v.size());
bool fir = true;
for(int i=0; i<v.size(); i++) {
if(u[i]) continue;
int idx = -1;
for(int j=i+1; j<v.size(); j++) {
if((v[i] + v[j]) % 10 == 0 && !u[j]) idx = j;
}
if(idx != -1) {
if(fir) fir = false;
else cout << "+";
cout << v[i] << "+" << v[idx];
u[i] = u[idx] = true;
}
}
for(int i=0; i<u.size(); i++)
if(!u[i]) {
if(fir) fir = false;
else cout << "+";
cout << v[i];
}
cout << "\n";
}
}
백준 BOJ 11504번 : 돌려 돌려 돌림판
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
돌림판의 한 칸에 숫자가 한 개씩 적혀있고, 그 중 한 칸을 골라 시계방향으로 선택한 수들을 이어붙인 수가 두 수 사이의 값이 되는 경우를 모두 구하는 문제이다.
문제에서 말한 경우를 모두 세어주기만 하면 된다.
어떻게 보면 구현 문제에 가깝다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N, M; cin >> N >> M;
string a = "", b = "";
for(int i=0; i<M; i++) {
char c; cin >> c;
a += c;
}
for(int i=0; i<M; i++) {
char c; cin >> c;
b += c;
}
vector<char> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int ans = 0;
for(int i=0; i<N; i++) {
string tmp = "";
for(int j=0; j<M; j++) tmp += v[(i+j) % N];
if(tmp >= a && tmp <= b) ans++;
}
cout << ans << "\n";
}
}
백준 BOJ 11453번 : Rummikub
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
루미큐브 조각들이 주어질 때, 색이 같고 연속한 3개의 숫자가 있거나, 숫자가 같고 색이 모두 다른 3개의 타일이 존재하는지 찾아주는 문제이다.
2차원 배열을 만들어서 주어진 조각들을 모두 체크해주고, 숫자와 색들을 체크해보면서 조건을 만족하는 세트가 있는지 찾아주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
bool v[101][4] = {};
while(N--) {
string str; cin >> str;
int x = stoi(str.substr(0, str.length()-1));
char y = str.back();
if(y == 'b') v[x][0] = true;
else if(y == 'g') v[x][1] = true;
else if(y == 'r') v[x][2] = true;
else if(y == 'y') v[x][3] = true;
}
bool check = false;
for(int i=0; i<4; i++)
for(int j=3; j<=100; j++)
if(v[j-2][i] && v[j-1][i] && v[j][i]) check = true;
for(int i=1; i<=100; i++) {
int cnt = 0;
for(int j=0; j<4; j++)
if(v[i][j]) cnt++;
if(cnt >= 3) check = true;
}
if(check) cout << "YES\n";
else cout << "NO\n";
}
}
백준 BOJ 13450번 : László Babai
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
3개의 노드로 이루어진 2개의 그래프가 주어질 때, 이 두 개의 그래프가 isomorphism (동형) 관계인지를 파악하는 문제이다.
노드가 3개밖에 없으므로, 간선의 수가 같으면 동일한 그래프가 될 수 밖에 없다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
int a, b;
while(T--) {
int N; cin >> N;
for(int i=0; i<N; i++) cin >> a >> b;
int M; cin >> M;
for(int i=0; i<M; i++) cin >> a >> b;
if(N == M) cout << "yes\n";
else cout << "no\n";
}
}
백준 BOJ 13641번 : Grid de Largada
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
문제를 정확히는 이해 못했는데 주어진 두 개의 순열에 대해 한 순열을 최소 swap수로 swap하여 두 번째 순열을 만들기 위한 최소 횟수를 구하는 문제 같다.
첫 번째 순열을 1 2 3 .. N으로 만들어주고 번호를 매칭하여 두 번째 순열도 바꿔준다.
그 다음 버블 정렬을 하면서 swap 횟수를 count 해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N;
while(cin >> N) {
vector<int> v(N+1);
for(int i=1; i<=N; i++) {
int x; cin >> x;
v[x] = i;
}
vector<int> u(N+1);
for(int i=1; i<=N; i++) {
int x; cin >> x;
u[i] = v[x];
}
int ans = 0;
for(int i=1; i<N; i++)
for(int j=N; j>i; j--)
if(u[j-1] > u[j]) {
swap(u[j-1], u[j]);
ans++;
}
cout << ans << "\n";
}
}
백준 BOJ 18067번 : Accurate Movement
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
주어진 규칙에 따라 두 블럭을 이동시켜서, 왼쪽 끝에 붙어있는 두 블럭을 모두 오른쪽 끝으로 붙이는데 필요한 최소 이동 수를 구하면 된다.
그리디하게 접근하여 각 블럭을 이동할 수 있는 최대한 이동시키고, 오른쪽 끝 범위 이상으로 이동되면 그 때의 횟수를 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b, N; cin >> a >> b >> N;
int x = a, y = b, ans = 0;
while(true) {
x = y;
ans++;
if(x >= N) break;
y += b - a;
ans++;
}
cout << ans << "\n";
}
백준 18512번 : 점프 점프
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
한 명은 지점 a에서 출발하여 한 번에 x미터씩 이동하고, 나머지 한 명은 지점 b에서 출발하여 한 번에 y미터씩 이동할 때, 두 명이 같은 지점을 지나는 가장 작은 위치를 구하는 문제이다.
범위가 작아 브루트포스로 일일이 돌려보면서 확인이 가능하다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b, x, y; cin >> a >> b >> x >> y;
for(int i=0; i<1e5; i++) {
if(x == y) {
cout << x << "\n";
return 0;
}
if(x < y) x += a;
else if(x > y) y += b;
}
cout << -1 << "\n";
}
백준 20240번 : Integer Square
문제 난이도 : Bronze I
알고리즘 분류 : 브루트포스
한 변의 길이의 제곱이 x인 정사각형의 네 정수 좌표를 아무거나 구하면 되는 문제이다.
원점을 기준으로 다른 지점까지의 거리의 제곱이 x인 지점을 찾아서, 90도씩 돌려서 나머지 점들을 찍어주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int a = -1, b = -1;
bool check = false;
for(int i=0; i<=1000; i++) {
for(int j=0; j<=1000; j++)
if(i*i + j*j == N) {
a = i, b = j;
check = true;
break;
}
if(check) break;
}
if(a == -1 && b == -1) {
cout << "Impossible\n";
return 0;
}
cout << 0 << " " << 0 << "\n";
cout << a << " " << b << "\n";
cout << -b << " " << a << "\n";
cout << -b + a << " " << a + b << "\n";
}