전체미궁
프로기만러
00:12:39
100
클리어 30명
참여 34명
퍼즐 규칙:
굵은 선으로 구분되어있는 4개의 4*4 구간에는 각각 8개의 9와 0이 들어가야 한다.
모든 화살표를 따라서 8개의 숫자를 읽었을 때 올바른 90이 되어야 한다.
이미 퍼즐에 쓰여져 있는 9와 0은 지울 수 없다.
(위 예시는 화살표를 따라서 읽는 것을 위해서 있는 예시일 뿐, 실제 퍼즐과는 무관하다.)
(실제로 퍼즐은 8*8 짜리이다.)
올바른 90에 대한 힌트:
9와 0은 짝을 이룬다.
90은 되지만, 09는 되지 않는다.
p-> 와 p->->가 짝을 이루는 것과 비슷하다.
정답 출력 방식:
1행부터 8행까지 9가 있는 열의 위치를 출력하면 된다.
정답 출력 예시:
12342341
(첫 행에 12, 두 번째 행에 34, 3번째 행에 234, 4번째 행에 1)
위의 예시는 실제 답과 무관하고, 정답 출력 형식을 보여주기 위한 예시일 뿐이다.
퍼즐:
연습장:
힌트) 답의 길이는 32이다. 폰 유저들 화이팅!
BiouX
13461356346826781247257813452578
올바른 90 문자열은 올바른 괄호 문자열을 말한다. 키보드에서 9는 (, 0은 )를 뜻한다.
p->은 [, p->->는 ]를 뜻한다.
이제 퍼즐을 풀어보자.
9를 (로, 0을 )로 보고 문제를 풀었을 때 정답은 아래와 같다.
따라서 답은 13461356346826781247257813452578 이다.
정답은 하나라는 것은 코드를 돌려서 확인했다. 물론 손으로도 돌려봤고, 손이 더 빠르다는 것도 확인했다.
아래 코드를 돌리면 위와 같이 정답이 나온다.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
bool sx[9], sy[9]; //화살표 방향
int sum[3][3]; //4*4 칸에 있는 (의 개수
bool ans[10][10]; //8*8 짜리 퍼즐 정답 칸
vector <vector <int>> cnum; //길이 8의 올바른 괄호 문자열
void print() //정답 출력
{
for(int i=1;i<=8;i++)
{
for(int j=1;j<=8;j++)
{
if(ans[i][j]) printf("( ");
else printf(") ");
}
printf("\n");
}
printf("\n\n\n");
}
void make_catalan_number() //올바른 괄호문자열 만들기
{
bool Check[9];
vector <int> tmp;
for(int i=1;i<=8;i++)
{
for(int j=i+1;j<=8;j++)
{
for(int k=j+1;k<=8;k++)
{
for(int l=k+1;l<=8;l++)
{
for(int o=1;o<=8;o++) Check[o]=false;
Check[i]=Check[j]=Check[k]=Check[l]=true;
int tsum=0, cnt=0;
for(int o=1;o<=7;o+=2) //올바른 괄호문자열은 1번째부터 2k+1번째까지 봤을 때 k+1개 이상의 (가 있음
{
tsum+=Check[o-1]+Check[o];
if(tsum>=(o+1)/2) cnt++;
}
if(cnt==4)
{
tmp.clear();
tmp.push_back(i);
tmp.push_back(j);
tmp.push_back(k);
tmp.push_back(l);
cnum.push_back(tmp);
}
}
}
}
}
}
void f(int x)
{
if(x==5) //위쪽 2개의 4*4 정사각형에 들어간 (의 개수가 8개인지 확인
{
int tsum=0; // ( 개수
for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) tsum+=ans[i][j];
if(tsum!=8) return;
}
if(x==9) //모든 열이 올바른 괄호 문자열인지 확인
{
for(int i=1;i<=8;i++)
{
if(sy[i]) //화살표가 아랫방향
{
int tsum=0; //( 괄호의 개수
bool jogun=true; //모든 열이 올바른 괄호문자열인지 체크
for(int j=1;j<=7;j+=2) //j가 홀수일 때 1행 i열부터 j행 i열까지 (의 개수가 )의 개수보다 많음
{
tsum+=ans[j][i]+ans[j-1][i];
if(tsum<(j+1)/2)
{
jogun=false;
break;
}
}
if(!jogun) return;
}
else //화살표가 아랫방향
{
int tsum=0;
bool jogun=true;
for(int j=8;j>=2;j-=2)
{
tsum+=ans[j+1][i]+ans[j][i];
if(tsum<(10-j)/2)
{
jogun=false;
break;
}
}
if(!jogun) return;
}
}
sum[0][0]=sum[0][1]=sum[1][0]=sum[1][1]=0;
for(int i=1;i<=8;i++)
{
for(int j=1;j<=8;j++)
{
sum[(i-1)/4][(j-1)/4]+=ans[i][j];
}
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
if(sum[i][j]!=8) return;
}
}
print();
return;
}
for(auto ele : cnum) //모든 길이 8 괄호 문자열을 다 시도해봄
{
for(int i=1;i<=8;i++) ans[x][i]=false;
if(sx[x]) for(int nxt : ele) ans[x][nxt]=true; //화살표가 오른쪽 방향인 경우
else for(int nxt : ele) ans[x][9-nxt]=true; //화살표가 왼쪽 방향인 경우
if(ans[4][5] || ans[2][4] || ans[4][3] || ans[5][3] || ans[7][2]) //지정된 숫자들을 바꾼 경우
{
ans[4][5]=ans[2][4]=ans[4][3]=ans[5][3]=ans[7][2]=false;
continue;
}
if(x==5 && !ans[5][7]) //지정된 숫자를 무시한 경우
{
continue;
}
f(x+1);
}
}
int main()
{
sx[1]=sx[2]=sx[5]=sx[7]=true; //화살표 위치 정하기
sy[1]=sy[3]=sy[4]=sy[6]=true; //화살표 위치 정하기
make_catalan_number();
ans[1][1]=ans[1][3]=ans[1][4]=ans[1][6]=true; //1행은 이미 정답이 고정됨
f(2);
}