[백준/C++]1018번(체스판 다시 칠하기), 1436번(영화감독 숌)

이수진·2022년 3월 10일
0

첫 번째 문제는 다음과 같습니다.

일일이 다 구하는 브루트포스 문제 입니다!
말 그대로 체스판의 두 가지 경우에 수에 대해(시작이 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;
 }
profile
꾸준히, 열심히, 그리고 잘하자

0개의 댓글