첫 번째 문제는 다음과 같습니다.
일일이 다 구하는 브루트포스 문제 입니다!
말 그대로 체스판의 두 가지 경우에 수에 대해(시작이 B인지, W인지)서 구해주면 됩니다.
이 문제를 처음 제출하고 나서 몇퍼센트에서 틀렸습니다가 계속 떴는데,
거의 한시간 동안 어디서 틀렸는지 계속 찾다가 마지막에서야 찾아냈습니다.
저는 이전까지 그냥 비교해서 틀리면 cnt변수를 ++해주어서 바꿔야 하는 만큼 계속 갱신해주었는데,
8 x 8 체스판에서 바꿔야 하는 max의 경우는 32입니다.
🔥즉, cmp의 개수가 32가 넘어가면, cmp의 값을 64에서 빼 주어야 한다는 것입니다.🔥
테스트 케이스로 돌려보다가 문제에 있는 이 예시
를 통해 알아냈습니다.
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int a[51][51]={0 };
int c[8][8]={
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1}
};
int d[8][8]={
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1, 0}
};
int n, m, res=63;
cin>>n>>m;
for(int i=0; i<n; i++){
string str; cin>>str;
for(int j=0; j<str.size(); j++){
if(str[j]=='W') a[i][j]=0;
else a[i][j]=1;
}
} // 입력끝
int start=-1;
for(int i=0; i<=n-8; i++){
for(int j=0; j<=m-8; j++){
start = a[i][j];
int tmp=0;
if(start==1){
// c랑 비교
for(int k=0; k<8; k++){
for(int l=0; l<8; l++){
if(a[i+k][j+l]!=c[k][l]) tmp++;
}
}
}
else{
// d랑 비교
for(int k=0; k<8; k++){
for(int l=0; l<8; l++){
if(a[i+k][j+l]!=d[k][l]) tmp++;
}
}
}
// 비교 끝
tmp=min(tmp, 64-tmp); // 주의
res=min(res, tmp);
}
}
cout<<res<<endl;
return 0;
}
두 번째 문제는 다음과 같습니다.
1부터 입력받은 n번째에 해당하는 종말의 숫자를 구하면 됩니다.
6이 "연속해서 나타난다"라는 것만 주의하면 될 것 같습니다.
저는 연속하는 6의 개수를 구할 때,
문자가 6일 때는 변수 cnt를 ++하고,
이 외의 경우는 cnt를 0으로 초기화 하여,
연속하는 6의 개수를 변수 cnt에 담았습니다.
그리고 연속하는 6의 개수가 가장 큰 경우를 변수 m에 담았고, 이를 계속해서 갱신해주었습니다.
이에 해당하는 코드는 다음과 같습니다.
for(int j=0; j<str.size(); j++){
if(str[j]=='6') cnt++;
else cnt=0;
if(m<cnt) m=cnt;
}
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int i, n; cin>>n;
int num=0;
for(i=1; ; i++){
string str = to_string(i);
int cnt=0;
int m=0;
for(int j=0; j<str.size(); j++){
if(str[j]=='6') cnt++;
else cnt=0;
if(m<cnt) m=cnt;
}
if(m>=3) num++;
if(num==n) break;
}
cout<<i<<endl;
return 0;
}