solved.ac Grand Arena Party 풀어보기
solved.ac 사이트에 들어가봤는데 그랜드 아레나 파티 퍼즐 힌트라는 것을 하고 있길래 궁금해서 들어가봤다. 문제가 첫 번째부터 열 번째까지 있는데 한 문제 한 문제가 다 쉽지 않다. 여기에는 하나씩 문제들을 풀면서 풀이를 적어보겠다. 높은 수준의 지능이 요구되니 오랫동안 고민해보면 지능 상승(?)에 도움이 될 수도 있을 것 같다.
1. 첫 번째 이야기 - 카드
첫 번째 문제는 주어진 게 "cards.pdf"라는 파일만 주고 답을 입력하라고 한다. 파일을 열어보면 이상한 문자들밖에 없다. 처음에는 뭘 해야할지 다 막막하다. 오래 고민하다 보니 문자들이 알파벳의 일부라는 사실을 알게 되었다. 그래서 이 문자들을 조합해서 의미있는 문자를 만들어야겠다고 생각했다. 문자들을 회전도 해보고 계속 조합해서 아래의 알파벳들을 만들었다.
F i N D O P E R A T i O N S
그래서 답에 FIND OPERATIONS를 입력해보았더니 맞았다.
2. 두 번째 이야기 - 실행
두 번째 문제는 이상한 엑셀 파일을 주고 답을 입력하라는 양심없는 문제이다. 파일을 잘 관찰하다보면 밑에 쪽에 return이 보인다.
이로부터 위에 있는 문자들로 코드를 입력해야한다는 것을 추측해볼 수 있다. 그리고 맨 앞에 #이 있으므로 #include ~를 생각해볼 수 있고 실제로 해보면 #include <stdio.h>가 가능하다. 노가다를 통해 문자들을 넣어보면..
#include <stdio.h>
int f(int n) {
if (n == 0) return 1;
int sum = 0;
for(int i=0;i<n;i++)
sum += f(i);
return sum % 13;
}
int main() {
char ans[] = "rgigmbuyhbfcx";
for (int i = 0; i< 13; i++)
ans[i] ^= f(13 + i*i*i);
puts(ans);
}이렇게 C언어 코드가 나온다. 근데 이걸 실행해보면 아무것도 안나오는데 TLE라서 그렇다. f(n)의 시간복잡도가 O(2^n)이나 나와서 시간초과가 발생한다. 그래서 이걸 수정시켜야 하는데 점화식을 보면 f(n) = 2 * f(n-1)이라는 것을 쉽게 알 수 있다. 이를 바탕으로 다시 코드를 짜보면...
#include <stdio.h>
int f(int n) {
if (n == 1) return 1;
return (2 * f(n - 1)) % 13;
}
int main() {
char ans[] = "rgigmbuyhbfcx";
for (int i = 0; i < 13; i++) {
ans[i] ^= f(13 + i * i * i);
}
puts(ans);
return 0;
}이렇게 되고 실행 결과 출력이 아래와 같이 나온다. 참고로 f(0) = 1일 때 해보면 출력값이 이상해서 f(1) = 1로 바꿔보았다.
se`ondtragedy
누가봐도 ' 이 c가 되어야할 것 같은 기분이 들기 때문에 정답으로 SECONDTRAGEDY를 입력해주면 정답이다!!
3. 세 번째 이야기 - 퍼즐
세 번째 문제는 그냥 백준 문제 8개만 풀면 돼서 그나마 괜찮았다.
<Problem Set>
A : Blocked Billboard
B : 지금 밥이 문제냐
C : 수강 변경
D : 영단어 암기는 괴로워
E : 고양이 카페
F : 5차 전직
G : 3차원 막대기 연결하기
H : 으어어… 에이쁠 주세요..
A.Blocked Billboard
그냥 2차원 배열로 좌표 만들어서 사각형들을 대응해주는 식으로 넓이를 구해도 쉽게 풀린다.
#include <iostream>
using namespace std;
bool coord[10000][10000];
int main()
{
int x1,y1,x2,y2,S=0;
cin>>x1>>y1>>x2>>y2;
x1 += 1000; y1 += 1000; x2 += 1000; y2 += 1000;
for(int m=x1;m<x2;m++)for(int n=y1;n<y2;n++) {S++; coord[m][n] = true;}
cin>>x1>>y1>>x2>>y2;
x1 += 1000; y1 += 1000; x2 += 1000; y2 += 1000;
for(int m=x1;m<x2;m++)for(int n=y1;n<y2;n++){
if(coord[m][n]) continue;
S++;
coord[m][n] = true;}
cin>>x1>>y1>>x2>>y2;
x1 += 1000; y1 += 1000; x2 += 1000; y2 += 1000;
for(int m=x1;m<x2;m++)for(int n=y1;n<y2;n++)if(coord[m][n]) S--;
cout<<S;
}
B : 지금 밥이 문제냐
이거는 그냥 문제에 나온대로 코딩하면 된다.
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <bitset>
using namespace std;
uint64_t ipv8ToUint64(const string& ipv8)
{
vector<int> parts;
stringstream ss(ipv8);
string part;
while (getline(ss, part, '.')) parts.push_back(stoi(part));
uint64_t result = 0;
for (int p : parts) result = (result << 8) + p;
return result;
}
string uint64ToIpv8(uint64_t num)
{
vector<int> parts(8);
for (int i = 7; i >= 0; --i) {
parts[i] = num & 0xFF;
num>>= 8;
}
stringstream ss;
for (size_t i = 0; i < parts.size(); ++i)
{
if (i != 0) ss<<".";
ss<<parts[i];
}
return ss.str();
}
int main()
{
int T;
cin>>T;
cin.ignore();
while(T--)
{
int M;
string N;
cin>>M>>N;
if (M == 1)
{
uint64_t result = ipv8ToUint64(N);
cout<<result<<endl;
}
else if (M == 2)
{
uint64_t num;
stringstream(N)>>num;
string result = uint64ToIpv8(num);
cout<<result<<endl;
}
}
}
C : 수강 변경
듣고 싶은 수업과 듣고 있는 수업이 모두 일대일 대응된다면 모두 자신이 듣고 싶은 수업을 적당한 변경을 통해 들을 수 있다. 그래서 듣고 싶은 수업의 개수에서 대응 가능한 듣고 있는 수업의 개수를 빼면 된다.
#include <iostream>
using namespace std;
int Class[1000001],N,n=0,c,w;
int main()
{
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>c;
Class[c] --;
}
for(int i=1;i<=N;i++)
{
cin>>w;
Class[w] ++;
}
for(int i=1;i<=1000000;i++) if(Class[i] > 0) n += Class[i];
cout<<n;
}
D : 영단어 암기는 어려워
이 문제는 unordered map과 sort함수를 잘 사용하면 구현은 쉽게 할 수 있다.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct WordInfo
{
string word;
int frequency;
int length;
};
bool compareWords(const WordInfo& a, const WordInfo& b)
{
if (a.frequency != b.frequency)
return a.frequency > b.frequency;
if (a.length != b.length)
return a.length > b.length;
return a.word < b.word;
}
int main()
{
int N,M;
cin>>N>>M;
unordered_map<string, int> wordCount;
vector<string> words(N);
for(int i=0;i<N;i++)
{
cin>>words[i];
if(words[i].length()>=M) wordCount[words[i]]++;
}
vector<WordInfo> wordInfos;
for(const auto& entry : wordCount) wordInfos.push_back({entry.first, entry.second, (int)entry.first.length()});
sort(wordInfos.begin(), wordInfos.end(), compareWords);
for(const auto& wordInfo : wordInfos)cout<<wordInfo.word<<"\n";
}
E : 고양이 카페
2개씩 짝을 지어서 제거해주면 되는데 오름차순으로 정렬한뒤 투포인터로 이터레이션해주면 쉽게 풀린다.
#include <iostream>
#include <algorithm>
using namespace std;
int N,K,weight[5000],n=0;
int main()
{
cin>>N>>K;
for(int i=0;i<N;i++) cin>>weight[i];
sort(weight,weight+N);
int l=0,r=N-1;
while(l<r)
{
if(weight[l] + weight[r] > K)
{
r --;
continue;
}
l ++; r --;
n ++;
}
cout<<n;
}
F : 5차 전직
재배열 부등식을 생각해보면 경험치가 큰 퀘스트를 수행할 때 가장 많은 아케인스톤을 가지고 있을 때 경험치를 최대로 받을 수 있을 것이다. 이에 맞춰서 코드를 짜주면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
long long n,k,ex[300000],maxExp=0;
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>ex[i];
sort(ex,ex+n);
for(long long i=1;i<n;i++)
{
if(k>i) maxExp += i*ex[i];
else maxExp += k*ex[i];
}
cout<<maxExp;
}
G : 3차원 막대기 연결하기
전형적인 기하 조건분기 문제이다. 크게 세 가지 경우로 나누어 해결할 수 있다. 만약 막대 길이의 총합이 최종 변위보다 작으면 당연히 불가능하다. 만약 같다면 그냥 쭉 이으면 되므로 가능하다. 마지막으로 더 큰 경우 최대 길이의 막대를 기준으로 봤을 때 삼각형 형성조건(일직선도 포함)을 이용하면 (나머지 길이)가 (가장 큰 길이) - (최종 변위)보단 커야함을 알 수 있다.
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int X1,X2,Y1,Y2,Z1,Z2,N,S=0,mx=0;
double dis;
int main()
{
cin>>X1>>Y1>>Z1>>X2>>Y2>>Z2;
dis = sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2) + (Z1 - Z2) * (Z1 - Z2));
cin>>N;
for(int i=1;i<=N;i++)
{
int l;
cin>>l;
S+=l;
int mx_k = mx;
mx = max(mx_k,l);
}
if(S<dis) cout<<"NO";
else if(S==dis) cout<<"YES";
else if(S-mx < mx - dis) cout<<"NO";
else cout<<"YES";;
}
H : 으어어... 에이쁠 주세요...
문제 자체는 간단하고 생각하기 쉽지만 구현하기가 좀 짜증나는 문제이다. 문제에 나온 그대로를 똑같이 코딩해주면 되는데 고려할 것들이 꽤 많아서 꼼꼼히 해야한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int, int>> zombie;
pair<int,int> way[4] = {make_pair(0,1),make_pair(-1,0),make_pair(0,-1),make_pair(1,0)};
vector<bool> zombieWay;
int N,map[20][20],l,x=1,y=1,w=0;
bool light[20][20];
string A;
void zombieMove()
{
for(int i=0;i<zombie.size();i++)
{
if(zombieWay[i])
{
if(zombie[i].second == N){zombieWay[i] = false; continue;}
zombie[i].second ++;
}
else
{
if(zombie[i].second==1){zombieWay[i] = true; continue;}
zombie[i].second --;
}
}
}
int main()
{
cin>>N>>A;
l = A.size();
for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)
{
char k; cin>>k;
if(k=='O') {continue;}
if(k=='S') {map[j][i] = 1; continue;}
zombie.push_back(make_pair(j,i));
zombieWay.push_back(true);
}
for(int i=0;i<l;i++)
{
if(A[i] == 'R') {w = (w + 1)%4;}
else if(A[i] == 'L') {w = (w + 3)%4;}
else {
int nextX = x + way[w].first, nextY = y + way[w].second;
if(nextX>0&&nextY>0&&nextX<=N&&nextY<=N)
{
x += way[w].first; y += way[w].second;
if(map[x][y] == 1)
{
for(int p=-1;p<=1;p++)for(int q=-1;q<=1;q++) light[x+p][y+q] = true;
}
if(!light[x][y]){
for(int p=0;p<zombie.size();p++)
{
if(zombie[p] == make_pair(x,y)) {cout<<"Aaaaaah!"; return 0;}
}
}
}
}
zombieMove();
if(light[x][y]) continue;
for(int p=0;p<zombie.size();p++)
{
if(zombie[p] == make_pair(x,y)) {cout<<"Aaaaaah!"; return 0;}
}
}
cout<<"Phew...";
}4. 네 번째 이야기 - 문제 셋 정하기
이 문제는 그냥 대화 내용만 주어주고 문제를 풀라는 노답 문제이다. 실제로 문제 셋 난이도 순서는 논리를 잘 따라가면 쉽게 구할 수 있고 순서는 아래와 같다.
G1 B5 B4 P5 S2
이제 이걸 가지고 답을 찾아야하는데 쉽게 안보인다. 그치만 가능한 난이도가 26개라는 것에 착안하여 접근해보자.
알파벳의 개수는 26개인데 이 개수와 동일하다. 그래서 알파벳에 각 난이도를 대응시킬 생각을 해볼 수 있다. 브론즈 5를 A에, 브론즈 4를 B에 이런 식으로 대응해 보면 아래왁 같은 문자열이 나온다.
TAB UI
이게 바로 정답이다.
5. 다섯 번째 이야기 - 입출력
아직 못품
6. 여섯 번째 이야기 - 십자말 풀었습니다!!
처음 이 문제를 봤을 때는 굉장히 당황해서 뭘 해야힐지 막막했었다. 그래서 각 문제들을 풀 때 사용되는 알고리즘이나 자료구조를 십자말에 넣는 것으로 시도해보았다. 근데 단어가 잘 떠오르지도 않고 관련이 있는 단어들은 글자수 때문에 넣을 수가 없었다. 그러다가 2번 문제랑 동일한 백준 문제를 본 적이 있던 거 같아서 찾아보았는데 백준에 2839번과 완벽히 같았다. 그래서 각 문제에 해당하는 번호를 넣어보기로 하였다.
그 결과 위와 같이 숫자들을 채워 넣었다. 여기서 a가 4,8, b가 5,8, c가 3, 8, d가 2,7, e가 5,8이 나온다.
7. 일곱 번째 이야기 - 핸들 끝말잇기
이건 친구가 필요한 문제이다. 대충 3명정도 끝말잇기를 하면 된다. 친구가 정 없다면 다른 계정 만들어서 해도 된다.
본인은 친한 친구와 성공했다.
8. 여덟 번째 이야기 - #bags
아직 못품
9. 아홉 번째 이야기 - 마법
이 화면이 프로필 배경 화면과 굉장히 유사하다는 것을 알 수 있다. 프로필 배경에 보면 Welcome Kit가 써져있는데 그걸 입력하면 정답이다.
10. 열 번째 이야기 - 바벨
아직 못품