이번에 새로 랜덤 마라톤 컨텐츠가 생겼다는 소식을 듣고 달려가서 해봤다.
티어가 낮아서 그런지 A문제를 뺀 나머지 문제가 전부 실버였다 ㅜㅜ
랜덤 문제는 지금까지 한 번 밖에 풀어본 적이 없어서, 이번 기회에 태그나 힌트를 안보면 문제를 얼마나 잘 풀지 확인 차 마라톤을 시작했다.
문제 + 풀이
문제를 풀 때 시간이 얼마나 걸리는지 같이 측정해야 실력이 어느정도 가늠이 될 것 같아서 시간을 재면서 풀었다.
[문제 후기]
A. Anti-Palindrome (17분)
문제 링크
가장 먼저 문제를 보자마자 영어로 되어있어서 당황했다;;
하지만 palindrome인지 검사하는 간단한 문제였다.
물론 palindrome을 효과적으로 검사하기 위해서는 대칭이라는 성질을 이용한 방법이 있지만, 이 문제는 string의 길이가 80밖에 되지 않는다.
그래서 2중 for문 + string 길이를 이용해 palindrome인지 판단하도록 코드를 구현했다.
구현
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
string str;
string reStr = "";
while (true) {
cin >> str;
if (cin.eof() == true) {
break;
}
for (int i = 0; i < str.length(); i++) {
if (str[i] != ' ') {
reStr += tolower(str[i]);
}
}
}
for (int i = 0; i < reStr.length(); i++) {
for (int j = i + 1; j < reStr.length(); j++) {
bool flag = true;
for (int k = 0; k <= (j - i)/2; k++) {
if (reStr[i + k] != reStr[j - k]) {
flag = false;
break;
}
}
if (flag) {
cout << "Palindrome";
return 0;
}
}
}
cout << "Anti-palindrome";
return 0;
}
B. 전국 대학생 프로그래밍 대회 동아리 연합 (11분)
문제 링크
처음 문제를 봤는데 아무리 봐도 문제가 이해가 되지 않았다;;
한 5분을 문제를 다시 읽기를 반복했더니, 각 호텔에서 2번째 줄에 i번째 값이 i번째 주에 머무를 수 있는 인원의 수 라는 것을 깨달았다...
그러므로 단순히 for문을 이용해 인원이 수용이 되는지, 예산을 넘는지 검사한 뒤 예산안에 인원이 수용된다면, 최소 비용을 지출하는 경우를 출력하면 되는 완전 탐색 문제다.
구현
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
const int INF = 987654321;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, B, H, W;
cin >> N >> B >> H >> W;
int minC = INF;
for (int i = 0; i < H; i++) {
int cost, P;
cin >> cost;
for (int j = 0; j < W; j++) {
cin >> P;
if (P >= N&&cost*N<=B) {
minC = min(minC, cost * N);
}
}
}
if (minC == INF) {
cout << "stay home";
}
else {
cout << minC;
}
return 0;
}
C. Binary Counting (24분)
문제 링크
최근에 재귀를 사용하는 문제를 많이 봐서 그런가 이진수로 변환하는 과정을 재귀로 빠르게 구현했다.
그런데 다음 과정에서 오래 걸렸다.
K번째 차례에 숫자를 외쳐야 하기 때문에 앞에 몇 명이 숫자를 외쳤는지만 계산해 K에서 빼주면 된다.
그런데 이 과정에서 괜히 index에 맞춰 K에 1을 뺄까 더할까 등 이상한 고민을 했고, 그 과정에서 헷갈려버렸다...
그냥 (이진수의 길이 % n) 값을 K에서 빼주고 K가 0보다 작으면 n을 더해주면 쉽게 해결된다.
그러면 K번째 순서를 계속 유지할 수 있다.
여기까지 풀었을 때, 시간이 오래걸려서 실력이 많이 모자란가... 생각이 들었다ㅠㅠ
구현
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
string binary(int num)
{
if (num == 0) {
return "0";
}
else if (num == 1) {
return "1";
}
else {
return binary(num / 2)+(num%2==1?"1":"0");
}
string retA;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int n, k;
cin >> n>>k;
int i = 0;
vector<char> v;
string tmpS;
k -= 1;
while (v.size()<5)
{
tmpS = binary(i);
for (int i = k; i < tmpS.length(); i+=n) {
v.push_back(tmpS[i]);
}
k -= tmpS.size() % n;
if (k < 0) {
k += n;
}
i++;
}
for (int i = 0; i < 5; i++) {
cout << v[i] << " ";
}
return 0;
}
D. Bowling (15분)
문제 링크
마찬가지로 영어문제라 당황했지만, 단순히 볼링 점수 계산을 구현하면 되는 문제다.
볼링 점수를 계산하는 방법을 경험으로 알고 있었기 때문에 단순한 조건문으로 열심히 구현했다.
덕분에 코드는 길어졌지만, 이전 문제보다 빠르게 풀 수 있었다.
추가로 한 게임에 대한 점수를 받을 때, 몇 번 공을 굴렸는지는 strike의 횟수에 영향을 받기 때문에 이를 고려해 입력을 받아야 한다.
구현
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
string binary(int num)
{
if (num == 0) {
return "0";
}
else if (num == 1) {
return "1";
}
else {
return binary(num / 2)+(num%2==1?"1":"0");
}
string retA;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N;
cin >> N;
int f, s;
for (int tc = 0; tc < N; tc++) {
vector<vector<int>> score(10,vector<int>(3,0));
int answer = 0;
for (int i = 0; i < 10; i++) {
if (i == 9) {
cin >> f;
if (f != 10) {
cin >> s;
score[9][0] = f, score[9][1]=s;
if (f + s == 10) {
cin >> f, score[9][2] = f;
}
}
else {
score[9][0] = f;
cin >> f, score[9][1] = f;
cin>>f, score[9][2] = f;
}
}
else {
cin >> f;
if (f != 10) {
cin >> s;
score[i][0] = f;
score[i][1] = s;
}
else {
score[i][0] = f;
score[i][1] = 0;
}
}
}
for (int i = 0; i < 10; i++) {
if (i != 9) {
if (score[i][0] == 10) {
if (i == 8) {
answer += score[i][0] + score[i+1][0] + score[i+1][1];
}
else {
if (score[i + 1][0] == 10) {
answer += score[i][0] + score[i + 1][0] + score[i + 2][0];
}
else {
answer += score[i][0] + score[i + 1][0] + score[i + 1][1];
}
}
}
else if (score[i][0] + score[i][1]==10) {
answer += score[i][0] + score[i][1] + score[i + 1][0];
}
else {
answer += score[i][0] + score[i][1];
}
}
else {
answer += score[i][0] + score[i][1] + score[i][2];
}
}
cout << answer << endl;
}
return 0;
}
E. 친구 (6분)
문제 링크
마라톤 중에 가장 빠르게 해결한 문제다.
N의 크기가 커봐야 50이기 때문에 단순한 반복문으로 완전 탐색해 빠르게 풀 수 있는 문제다.
for문으로 i번째 사람의 친구를 구하고, i번째 사람과 직접 연결된 사람이 있다면, 그 사람의 친구도 i번째 사람의 친구로 체크한다.
그렇게 친구인지 체크를 완료 했으면, 친구의 수를 비교해 친구수가 가장 많은 사람의 친구수를 출력하면 되는 문제다.
구현
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
ios::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];
}
int maxAnswer = 0;
for (int i = 0; i < N; i++) {
vector<bool> visited(N, false);
int answer = 0;
for (int j = 0; j < N; j++) {
if (v[i][j] == 'Y')
{
visited[j] = true;
for (int k = 0; k < N; k++) {
if (v[j][k] == 'Y') {
visited[k] = true;
}
}
}
}
for (int j = 0; j < N; j++) {
if (visited[j] && j != i) {
answer++;
}
}
maxAnswer = max(answer, maxAnswer);
}
cout << maxAnswer;
return 0;
}
F. Hot Springs (10분)
문제 링크
이 문제를 풀면서 백준보다 CodeForce에 가까운 느낌이 드는 문제라는 느낌을 받았다.
얼핏 보면 어려워 보이지만, 정렬을 사용하면 쉽게 풀 수 있는 문제다.
왜냐하면 정렬을 했을 경우 i와 i+1번째 수의 차이보다 i-1번째 수와 i+1번째 수의 차이가 크거나 같은 것은 자명한 사실이기 때문이다.
$$ n_{i-1} \leq n_{i},\;\;\;\; n_{i+1}-n_{i}\leq n_{i+1}-n_{i-1} $$
즉, 위 식이 성립하기 때문에 정렬 후 중앙에 있는 수를 기준으로 왼쪽 오른쪽의 수를 번갈아가며 출력하면 되는 문제다.
$$ abs(n_{i}-n_{i+1})\leq abs(n_{i+1}-n_{i-1})\leq abs(n_{i-1}-n_{i+2}) ...$$
구현
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++)
cin >> v[i];
sort(v.begin(), v.end());
int right = N / 2;
int left = right - 1;
while(true)
{
if (right < N) {
cout << v[right] << " ";
right++;
}
if (left >= 0) {
cout << v[left] << " ";
left--;
}
if (right >= N && left < 0) {
break;
}
}
return 0;
}
F. 헤이카카오 (20분)
문제 링크
기댓값을 구하는 방법을 알면 쉽게 풀 수 있는 문제다.
그런데, 처음에 기댓값을 구하는 과정에서 또 어떻게 하면 빠르게 풀 수 있을까 고민하다가 다시 삽질을 해 오래 걸렸다ㅜ
문제 푸는 방법을 요약하면 (i번째 끝말잇기 게임에 도달할 확률)*(현재 승리할 확률)*(끝말잇기를 하는데 걸린 시간)을 반복해서 더한 뒤, 소수점 7자리까지 표현하면 되는 문제다.
구현
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
double a,d,k;
cin >> a >> d >> k;
int nowTime = a;
d/=100;
double wholeCase = 1;
double retT = 0;
while (d < 1) {
// 걸린 시간 * 이길확률 * 경우의 수 확률 = 기댓값
// 다음으로 갈 확률
retT += nowTime * (d)*wholeCase;
wholeCase -= wholeCase * d;//이길 확률
d *= (k + 100) / 100;
nowTime += a;
}
retT += nowTime *wholeCase;
printf("%.7f", retT);
return 0;
}
F. 이집트 분수 (27분)
문제 링크
마라톤 문제 중 가장 시간이 오래 걸린 문제다.
처음에 문제를 대충 읽은 이유도 있지만, GCD를 이용하는 과정에서 문제가 있었다.
a를 b로 나눈 값이 0이 아니라면 a%b와 b의 GCD를 구해야 하는데, 무슨 생각인지 몰라도 a-b, b의 GCD를 구했다;;
이외에도 제한을 보니 int형대신 long long을 써야되겠다는 생각이 들어서 이것저것 수정하고 나니 시간이 오래걸린 문제였다
풀이 방법은 간단하다.
1. i를 2부터 999,999까지 탐색하면서 1/i를 뺀 값이 0보다 크거나 같으면서, 분모가 100만 이하인지 검사한다.
2. 1번 조건을 만족할 경우 다시 i값을 넣어 함수를 호출한 다음 탐색을 시작한다.
3. 위 과정을 반복해 0이 나오면 현재 호출한 함수들의 i값이 정답이다.
4. 만약 위 과정을 반복했는데, 0이 나오지 않으면 i의 값을 증가시켜 다시 탐색한다.
그림을 참고면 더 이해가 쉽다.
위 그림처럼 어떤 값을 return 하느냐에 따라서 i값을 건너뛰고 다음 i를 탐색할지 정해지는 함수를 만들어 문제를 해결했다.
+ 잘 생각해보니 1,000,000을 넘는지만 계산해 체크하면 되는 문제였다;; 재귀로 계산할 필요가 없었네 어차피 안들어가는데ㅠㅠ
구현
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
vector<int> answer;
long long GCD(long long a, long long b) {
if (a < b) {
return GCD(b, a);
}
if (a % b == 0) {
return b;
}
else {
return GCD(a % b, b);
}
}
bool Calc(long long m, long long n, long long st)
{
for (int i = st; i < 10000000; i++) {
if (i * m >= n) {
long long tmpN = n * i;
long long tmpM = i * m - n;
if (tmpM == 0) { //기저 사례
answer.push_back(i);
return true;
}
long long gcd = GCD(tmpN, tmpM);
if (tmpN / gcd >= 1000000) {
continue;
}
else
{
if (Calc(tmpM / gcd, tmpN / gcd, i)) {
answer.push_back(i);
return true;
}
else {
continue;
}
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
long long M, N;
while (true) {
answer=vector<int>(0);
cin >> M >> N;
if (M == 0 && N == 0) {
break;
}
long long st = 2;
Calc(M, N, st);
for (int i = answer.size() - 1; i >= 0; i--) {
cout << answer[i] << " ";
}
cout << "\n";
}
return 0;
}
[풀이 후기]
8개의 문제를 푸는데 총 2시간 10분이 걸렸다...
브론즈 문제와 실버 하위 문제가 포함되어 있었는데;;
처음에는 1시간 30분 내에 문제를 풀 수 있지 않을까? 생각했는데, 오판이었다ㅠㅠㅠ;;
확실히 랜덤으로 문제가 나오다보니 고민하는데 시간도 걸렸던 것 같다.
오히려 특정 알고리즘만 알면 풀 수 있는 골드 문제가 더 쉽게 느껴진다.
그리고 A부터 H까지 난이도가 상승하면서 문제가 주어지고 빠르게 문제를 푸려고 했더니 재밌던것 같다.
마라톤에서 골드 문제를 보려면 얼른 티어를 올려둬야겠다.
'Algorithm > BAEKJOON' 카테고리의 다른 글
| [백준/C++] 트리의 독립집합 (No. 2213) (1) | 2024.06.09 |
|---|---|
| [백준/C++] 최솟값 찾기 (No. 11003) (0) | 2024.06.06 |
| [백준/C++] ACM Craft (No. 1005) (0) | 2024.06.04 |
| [백준/C++] 트리와 쿼리 (No. 15681) (1) | 2024.06.03 |
| [백준/C++] 전력난 (No. 6497) (1) | 2024.06.02 |