백준 BOJ 4353번 : Beavergnaw
문제 난이도 : Silver IV
알고리즘 분류 : 기하학
지름이 D인 원통형 나무의 위아래 높이 차가 D인 부분을 파서 지름이 d이고 높이가 d인 원통형 나무를 남길 때, 파먹은 부분의 부피를 구하는 문제이다. (구체적인 형태는 위의 그림을 참고하자.)
문제의 조건에 따라 식을 정리하면 위와 같이 된다.
원뿔대의 부피는 1/3 pi H (r^2 + rR + R^R)인데 이것은 큰 원뿔의 부피에서 작은 원뿔의 부피를 (높이는 비례식으로 계산) 계산하여 얻을 수 있는 공식이다.
나머지는 관계식을 구해서 d를 구하면 되는데, 나의 경우에는 식을 풀기 귀찮아서 이분 탐색으로 해결했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(3);
while(true) {
double D, V; cin >> D >> V;
if(D == 0 && V == 0) break;
double l = 0, r = D;
while(l + 1e-5 < r) {
double m = (l + r)/2;
double V1 = (1.0/3.0) * M_PI * (1.0/2.0) * (D - m) * (D*D/4 + D*m/4 + m*m/4);
double Vt = M_PI*D*D*D/4 - 2*V1 - M_PI*m*m*m/4;
if(Vt > V) l = m;
else r = m;
}
cout << l << "\n";
}
}
백준 BOJ 24775번 : The Amazing Human Cannonball
문제 난이도 : Bronze I
알고리즘 분류 : 기하학, 물리학
사람을 수평으로부터 theta의 각도로 v0의 속도로 날릴 때, 발사 지점으로부터 x1만큼 떨어진 지점에서 h1 이상 h2 이하의 구간으로 여유 높이 1m를 남기고 통과할 수 있는지를 구하는 문제이다.
문제에서 운동 방정식을 다 줬기 때문에, 굳이 알고 있을 필요 없이 있는 식에다가 대입만 해줘도 쉽게 풀린다.
x1을 대입하여 t를 x1에 대해 정리하고, 이 t를 y에 대한 방정식에 대입하여 y 값을 나타내어주면 된다.
이제 이 y가 h1과 h2에 대해 여유 높이 1m를 가지면 된다.
#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--) {
double v0, th, x1, h1, h2;
cin >> v0 >> th >> x1 >> h1 >> h2;
th = th * M_PI / 180.0;
double y = x1 * tan(th) - (9.81 * x1 * x1) / (2 * v0 * v0 * cos(th) * cos(th));
if(h1 + 1 < y && y < h2 - 1) cout << "Safe\n";
else cout << "Not Safe\n";
}
}
백준 BOJ 11773번 : ESEJ
문제 난이도 : Silver V
알고리즘 분류 : 구성적, 무작위화
주어진 a, b에 대해 a 이상 b 단어를 가지고 단어의 종류가 b/2 종류 이상인 문장을 출력하는 문제이다.
중복을 제외하고는 단어의 구성에 대한 제약은 없으므로 아무 알파벳이나 조합하면 된다.
또한 b/2 종류 이상의 단어를 출력해야 하므로 a가 작은 경우 a 종류만 출력했을 때 조건에 어긋날 수 있다.
따라서 b 종류의 단어를 출력하되, i번째 단어를 출력할 때 (i + 1)을 26진수 알파벳으로 바꾼 단어를 출력하도록 하여 모든 단어가 달라질 수 있도록 구현하였다.
#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, M; cin >> N >> M;
for(int i=0; i<M; i++) {
int temp = i + 1;
string str = "";
while(temp > 0) {
str += char(temp % 26 + 'a');
temp /= 26;
}
cout << str << " ";
}
cout << "\n";
}
백준 BOJ 14584번 : 암호 해독
문제 난이도 : Silver V
알고리즘 분류 : 문자열, 브루트포스
주어진 문자열에 카이사르 문자열처럼 shift를 적용시킬 때, 주어진 N개의 단어 중 하나를 포함하는 문자열을 구하는 문제이다.
브루트포스로 26가지의 shift를 모두 수행해보며 N개의 단어 중 하나라도 포함한다면 그 문자열을 출력해주면 된다.
문자열을 포함하는지 체크할 때는 substr 함수를 활용하여 반복문을 돌려주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
string str; cin >> str;
int N; cin >> N;
vector<string> v(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<26; i++) {
string temp = str;
for(int j=0; j<temp.length(); j++)
temp[j] = char('a' + (temp[j] - 'a' + i) % 26);
bool check = false;
for(int j=0; j<N; j++) {
if(v[j].length() > temp.length()) continue;
for(int k=0; k<temp.length()-v[j].length()+1; k++)
if(temp.substr(k, v[j].length()) == v[j]) check = true;
}
if(check) {
cout << temp << "\n";
break;
}
}
}
백준 BOJ 23253번 : 자료구조는 정말 최고야
문제 난이도 : Silver V
알고리즘 분류 : 애드 혹
M개의 책 더미가 있고 이들은 1부터 N까지의 숫자가 한 번씩만 등장하며, 각 더미의 맨 위의 책만 꺼낼 수 있다고 할 때 1부터 N까지의 책을 순서대로 꺼낼 수 있는지의 여부를 구하는 문제이다.
각 더미에서 역순으로 쌓인 번호 관계만 존재하지 않는다면 모든 책을 꺼낼 수 있다.
#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, M; cin >> N >> M;
bool check = true;
while(M--) {
int K; cin >> K;
vector<int> v(K);
for(int i=0; i<K; i++) cin >> v[i];
for(int i=1; i<K; i++)
if(v[i-1] < v[i]) check = false;
}
if(check) cout << "Yes\n";
else cout << "No\n";
}
백준 BOJ 9324번 : 진짜 메시지
문제 난이도 : Silver V
알고리즘 분류 : 문자열
문자열에서 어떤 문자가 세 번째 등장할 때마다 문자가 2개씩 나오는 메시지가 진짜 메시지라고 할 때, 주어진 문자열이 진짜 메시지인지의 여부를 구하는 문제이다.
26개의 문자의 개수를 count 해주다가 3의 배수에 도달했을 때 뒤에 문자가 존재하면서 그 문자가 현재 문자와 같은지만 검사해주면 된다.
이 때 다음 문자는 count에 포함하면 안되므로 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--) {
string str; cin >> str;
int cnt[26] = {};
bool check = true;
for(int i=0; i<str.length(); i++) {
cnt[str[i] - 'A']++;
if(cnt[str[i] - 'A'] % 3 == 0) {
if(i+1 >= str.length()) check = false;
else if(str[i+1] != str[i]) check = false;
i++;
}
}
if(check) cout << "OK\n";
else cout << "FAKE\n";
}
}
백준 BOJ 23544번 : Kinder Surprise
문제 난이도 : Bronze I
알고리즘 분류 : 정렬
N개의 서로 다른 상품이 있고 N개의 현재 뽑은 상품 리스트가 주어질 때, 아직 뽑지 못한 상품의 종류의 수를 구하는 문제이다.
N개의 문자열 중에서 중복되는 것의 수를 구하면 된다.
따라서 중복인 것을 제거하고 벡터의 크기와 N의 차이를 답으로 구하면 된다.
문제 분류가 '트리를 사용한 집합과 맵'으로 되어있던데 그건 어떤 풀이인지 잘 모르겠다.
#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;
vector<string> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
cout << N - v.size() << "\n";
}
백준 BOJ 8321번 : Tables
문제 난이도 : Bronze I
알고리즘 분류 : 그리디, 정렬
N개의 상자에 못이 들어있고, a개의 테이블을 만들 것이고 각 테이블당 b개의 못이 들어있을 때 최소 몇 개의 상자가 필요한지 구하는 문제이다. (a_i에 대해 각 상자에 든 못 개수가 주어진다.)
못이 많이 든 상자부터 취하며 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);
int N, a, b; cin >> N >> a >> b;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end(), greater<int>());
int ans = 0, sum = 0;
for(int i=0; i<N; i++) {
sum += v[i];
if(sum >= a * b) {
cout << i + 1 << "\n";
break;
}
}
}
백준 BOJ 6799번 : Computer Purchase
문제 난이도 : Bronze I
알고리즘 분류 : 정렬
컴퓨터의 이름과 R, S, D의 값이 주어졌을 때, 2R + 3S + D 값이 큰 컴퓨터를 선호하고 만약 값이 같다면 컴퓨터의 이름이 사전순으로 앞서는 것을 선호한다면, 가장 선호하는 2개의 컴퓨터의 이름을 구하는 문제이다.
간단한 정렬 문제이지만, N의 입력이 1 또는 0이 들어올 수 있다.
이런 유형의 문제에서 N이 0이 들어오는 문제는 처음봐서 어디가 틀렸나 싶었다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool cmp(pair<string, int> x, pair<string, int> y) {
if(x.second != y.second) return x.second > y.second;
else return x.first < y.first;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<string, int>> v(N);
for(int i=0; i<N; i++) {
int a, b, c;
cin >> v[i].first >> a >> b >> c;
v[i].second = a*2 + b*3 + c;
}
if(N == 0) return 0;
if(N == 1) {
cout << v[0].first << "\n";
return 0;
}
sort(v.begin(), v.end(), cmp);
cout << v[0].first << "\n" << v[1].first << "\n";
}
백준 BOJ 5078번 : Shirts
문제 난이도 : Bronze I
알고리즘 분류 : 정렬
2자리 알파벳으로 이루어진 문자열을 정렬하는데, 앞자리는 무조건 S, M, L 순으로 배치되어야 하고 만약 앞자리가 같다면 나머지는 알파벳 순으로 배치하는 문제이다.
간단한 정렬 문제로, compare 함수를 따로 정의하여 sort를 해주면 된다.
cmp 함수의 자세한 구현은 코드를 참고하자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool cmp(string a, string b) {
if(a[0] != b[0]) {
if(a[0] == 'S') return true;
else if(b[0] == 'S') return false;
else if(a[0] == 'M') return true;
else return false;
}
return a[1] < b[1];
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N; cin >> N;
if(N == 0) break;
vector<string> v;
while(N--) {
string str; cin >> str;
v.push_back(str);
}
int M; cin >> M;
while(M--) {
string str; cin >> str;
v.push_back(str);
}
sort(v.begin(), v.end(), cmp);
for(int i=0; i<v.size(); i++) cout << v[i] << " ";
cout << "\n";
}
}
백준 BOJ 15066번 : Happy Trails
문제 난이도 : Bronze I
알고리즘 분류 : 기하학
N개의 구간에 대해, 각 구간의 수평으로부터의 각도와 구간 길이가 주어진다면 N개의 구간을 통과한 후의 높이를 구하는 문제이다.
구간의 길이가 x이고 수평으로부터의 각이 theta라면 그 구간을 통과한 이후의 고도 변화는 x sin(theta)이므로, 이들의 합을 구해주면 된다.
#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;
double ans = 0;
while(N--) {
double th, x; cin >> th >> x;
th = th * M_PI / 180.0;
ans += x * sin(th);
}
cout << fixed;
cout.precision(2);
cout << ans << "\n";
}
백준 BOJ 11337번 : Largest inscribed rectangle
문제 난이도 : Bronze I
알고리즘 분류 : 기하학
반지름이 R인 원에 내접하는 직사각형 중 짧은 변의 길이가 B 이상인 것의 넓이의 최댓값을 구하는 문제이다.
먼저 원에 내접하는 가장 큰 직사각형의 넓이는, 반지름이 sqrt(2) R인 정사각형이다.
따라서 이를 제곱한 2R^2을 답으로 구해주면 되지만, 만약 sqrt(2) R 값이 B보다 크다면 한 변의 길이를 B로 고정하고 답을 구해야 한다.
이 경우 답은 B * sqrt(4R^2 - B^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);
cout << fixed;
cout.precision(3);
int T; cin >> T;
while(T--) {
double R, B; cin >> R >> B;
if(sqrt(2)*R <= B) cout << 2*R*R << "\n";
else cout << B * sqrt(4*R*R - B*B) << "\n";
}
}
백준 BOJ 4934번 : The Euclidian Clock
문제 난이도 : Bronze I
알고리즘 분류 : 기하학
아날로그 시계에 나타나는 두 시간(시, 분, 초, 1/100초)이 주어질 때, 두 시침이 이루는 부채꼴의 넓이를 구하는 문제이다.
전체를 1이라고 가정하고 그에 대한 비율을 이용하여 답을 구하면 된다.
예를 들어 시침이 가리키는 시간이 5시, 분침이 가리키는 시간이 30분이라면 5 * (1/12) + 30 * (1/(12*60))과 같이 전체 1에 대한 비율을 구할 수 있다.
이제 이 비율 차이를 구한 뒤 전체 원의 면적에 곱하면 답을 얻을 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(3);
int T; cin >> T;
for(int t=1; t<=T; t++) {
double h1, m1, s1, u1;
cin >> h1 >> m1 >> s1 >> u1;
double x1 = h1/12 + m1/(12*60) + s1/(12*60*60) + u1/(12*60*60*100);
double h2, m2, s2, u2;
cin >> h2 >> m2 >> s2 >> u2;
double x2 = h2/12 + m2/(12*60) + s2/(12*60*60) + u2/(12*60*60*100);
double r; cin >> r;
double ans = M_PI * r * r * (x2 - x1);
cout << t << ". " << ans << "\n";
}
}
백준 BOJ 11172번 : Election
문제 난이도 : Bronze I
알고리즘 분류 : 기하학
N개의 점과 반지름이 주어질 때, 한 점의 영역을 그 점을 중심으로 반지름을 그리는 원이라고 하자.
다른 점들의 영역과 가장 많이 겹치는 점의 이름을 구하는 문제이다.
두 점 사이의 거리가 두 원의 반지름의 합보다 짧으면 영역이 생기므로, 브루트포스 알고리즘으로 모든 쌍을 비교해보면서 몇 개의 영역과 겹치는지 모든 원에 대해서 세어주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { string str; double x, y, r; };
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
vector<s> v(N);
for(int i=0; i<N; i++)
cin >> v[i].str >> v[i].x >> v[i].y >> v[i].r;
vector<int> u(N);
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) {
if(i == j) continue;
if(pow(v[i].x - v[j].x, 2) + pow(v[i].y - v[j].y, 2) <= pow(v[i].r + v[j].r, 2)) u[i]++;
}
int Max = 0;
for(int i=0; i<N; i++) Max = max(Max, u[i]);
int cnt = 0, idx;
for(int i=0; i<N; i++)
if(u[i] == Max) {
cnt++;
idx = i;
}
if(cnt >= 2) {
cout << "TIE\n";
continue;
}
cout << v[idx].str << "\n";
}
}
백준 BOJ 23274번 : Joint Jog Jam
문제 난이도 : Bronze II
알고리즘 분류 : 기하학
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);
vector<pair<double, double>> v(4);
for(int i=0; i<4; i++)
cin >> v[i].first >> v[i].second;
double s1 = sqrt(pow(v[0].first - v[1].first, 2) + pow(v[0].second - v[1].second, 2));
double s2 = sqrt(pow(v[2].first - v[3].first, 2) + pow(v[2].second - v[3].second, 2));
cout << fixed;
cout.precision(6);
cout << max(s1, s2) << "\n";
}
백준 BOJ 14758번 : Paint Me
문제 난이도 : Bronze II
알고리즘 분류 : 구현
방의 가로, 세로, 높이가 주어지고 창문과 문 등의 면적, 그리고 페인트 한 통당 칠할 수 있는 면적이 주어진다고 할 때, N개의 방의 문이나 창문을 제외한 옆면과 천장을 칠하는데 필요한 페인트의 수를 구하는 문제이다.
옆면과 천장의 총 면적을 구하고 문과 창문들의 넓이를 뺀 뒤 N배 하여 답을 구해주면 된다.
#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 N, w, l, h, a, M;
cin >> N >> w >> l >> h >> a >> M;
if(N == 0 && w == 0 && l == 0 && h == 0 && a == 0 && M == 0) break;
int sum = w*h*2 + l*h*2 + w*l;
while(M--) {
int x, y; cin >> x >> y;
sum -= x * y;
}
sum *= N;
int ans = (sum - 1)/a + 1;
cout << ans << "\n";
}
}
백준 BOJ 11113번 : The Traveling Orienteerer
문제 난이도 : Bronze II
알고리즘 분류 : 구현
N개 점들의 위치가 주어지고, K개의 점들의 번호 목록이 주어질 때, 1번째 점에서 시작하여 2, 3, ... 번째 점들을 거쳐 K번째 점에 도달하는 경로를 구하는 문제이다.
문제 그대로 구현해주면 된다.
점과 점 사이 거리를 피타고라스 정리를 이용하여 구해주고, 이 구간들의 합을 구해주면 되는 단순한 문제이다.
마지막에 단순 내림 처리가 아닌 반올림 처리를 해야함에 주의하자.
#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;
vector<pair<double, double>> v(N);
for(int i=0; i<N; i++) cin >> v[i].first >> v[i].second;
int M; cin >> M;
while(M--) {
int K; cin >> K;
vector<int> u(K);
for(int i=0; i<K; i++) cin >> u[i];
double ans = 0;
for(int i=1; i<K; i++)
ans += sqrt(pow(v[u[i-1]].first - v[u[i]].first, 2) + pow(v[u[i-1]].second - v[u[i]].second, 2));
cout << round(ans) << "\n";
}
}
백준 BOJ 3512번 : Flat
문제 난이도 : Bronze III
알고리즘 분류 : 구현
방의 수 N, 평당 가격 M, 그리고 N개의 줄에 걸쳐 면적과 그 방의 종류가 주어질 때, 총 면적과 침실의 면적, 그리고 (기타 면적 + 발코니 면적/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 N, M; cin >> N >> M;
int bed = 0, bal = 0, oth = 0;
for(int i=0; i<N; i++) {
int x; cin >> x;
string str; cin >> str;
if(str == "bedroom") bed += x;
else if(str == "balcony") bal += x;
else oth += x;
}
cout << bed + bal + oth << "\n";
cout << bed << "\n";
cout << fixed;
cout.precision(6);
cout << ((double)bal/2 + bed + oth) * M << "\n";
}
백준 BOJ 15600번 : Boss Battle
문제 난이도 : Bronze II
알고리즘 분류 : 구현, 게임 이론
원형의 N개의 점이 있고 그 중 하나에 폭탄을 놓으면 좌우로 한 칸까지 폭발하며, 보스는 한 칸에 숨어있는데 한 번의 폭탄 공격마다 인접한 한 칸으로 이동할 수 있다고 할 때 최악의 경우 몇 개의 폭탄을 설치해야 보스를 잡을 수 있는지 구하는 문제이다.
일단 한 칸에 폭탄을 설치했는데 게임이 계속 진행된다면 일단 그 칸에는 보스가 없다고 확신할 수 있다.
왜냐하면 인접한 칸으로 이동해도 그 칸까지 공격 범위이기 때문이다.
따라서 한 칸씩 설치해가면서 마지막 3칸이 남을 때까지 설치를 해봐야 최악의 경우에도 위치를 확실히 알 수 있다.
단, 3칸 이하인 경우는 똑같이 답이 1이므로 예외처리를 해주어야 한다.
#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;
if(N <= 3) cout << 1 << "\n";
else cout << N - 2 << "\n";
}
백준 BOJ 21287번 : Färgrobot
문제 난이도 : Bronze II
알고리즘 분류 : 그리디
R, G, B로만 이루어진 문자열이 있을 때 문자열의 맨 왼쪽에서 시작하여 하나의 문자를 말하면 그 문자를 만날 때까지 오른쪽으로 이동한다고 하자.
N개 이하의 명령을 내려 최대한 오른쪽으로 가기 위한 명령을 구하는 문제이다.
그리디적으로 접근하여 지금 위치에서 가장 먼 문자를 명령으로 내리면 된다.
단순히 반복문을 이용하여 두 개의 문자를 만나면 나머지 한 문자를 명령에 추가하고 그 문자가 나올 때까지 이동하는 방식으로 구현하였다.
#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;
string str; cin >> str;
string ans = "";
bool b[3] = {};
for(int i=0; i<str.length(); i++) {
if(str[i] == 'R') b[0] = true;
else if(str[i] == 'G') b[1] = true;
else b[2] = true;
if(b[0] && b[1]) {
while(str[i] != 'B') i++;
ans += 'B';
b[0] = b[1] = b[2] = false;
}
else if(b[1] && b[2]) {
while(str[i] != 'R') i++;
ans += 'R';
b[0] = b[1] = b[2] = false;
}
else if(b[2] && b[0]) {
while(str[i] != 'G') i++;
ans += 'G';
b[0] = b[1] = b[2] = false;
}
if(ans.length() == N) break;
}
cout << ans << "\n";
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 풀이 : Disjoint set, 유니온 파인드 문제들 풀이 220809 (0) | 2022.08.09 |
|---|---|
| 백준 BOJ 문제 풀이 모음 220804 (0) | 2022.08.04 |
| 백준 BOJ 기하, 에라토스테네스의 체, DP 등등.. 220802 (0) | 2022.08.02 |
| 백준 BOJ 에라토스테네스의 체, 소수 판별 문제들 풀이 220801 (0) | 2022.08.01 |
| 백준 BOJ 풀이 : 다양한 유형 및 백트래킹 문제들 220731 (0) | 2022.07.31 |