백준 및 코드포스

문제가 귀찮지만, 하나씩 뜯어보면 어렵지 않다. 

아무래도 '구현' 문제니까, 정답을 보기 전에 직접 구현해보기를 추천한다~~

구현사항이 많다.

• 궁수 3마리 배치
• bfs로 가까운 적 찾기
• 적 삭제
• 적 이동
• 게임 종료

위의 사항들을 주석을 달아서 분리하거나, 함수화하여 문제를 해결하면 그래도 가독성 있게, 디버깅 쉽게 해결할 수 있다.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int n,m,d, ans;
int arr[16][16], brr[16][16];
int dx[4] = {0, -1, 1,0}, dy[4] = {-1, 0, 0, 1};
queue< pair< int, int > > Q;

void bfs(int bow) {
  int vis[16][16] = {};
  auto bowP = make_pair(n, bow);
  vis[n][bow] = 1;

  Q.push(bowP);

  bool flag = 0;
  
  while(!Q.empty()) {
    auto cur = Q.front(); Q.pop();
    for(int i = 0; i < 4; i++) {
      int nx = cur.first + dx[i];
      int ny = cur.second + dy[i];
      if(nx < 0 || nx >= n + 1 || ny < 0 || ny >= m + 1) continue;
      
      if(vis[nx][ny]) continue;

      if(brr[nx][ny]) {
        vis[nx][ny] = vis[cur.first][cur.second] + 1;
        brr[nx][ny] = 2;
        flag = 1;
        break;
      }
      vis[nx][ny] = vis[cur.first][cur.second] + 1;
      if(vis[cur.first][cur.second] + 1 > d) continue;
      Q.push(make_pair(nx, ny));
    }
    if(flag) break;
  }

  while(!Q.empty()) Q.pop();
}

void fight(int fir, int sec, int thi) {

  int tmp = 0;

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      brr[i][j] = arr[i][j];
    }
  }

  bool repeat = 1;

  while(repeat) {
    repeat = 0;
    
    // 궁수 하나씩 제일 가까운 적 찾기
    bfs(fir);
    bfs(sec);
    bfs(thi);  

    // 그 적 삭제하기
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        if(brr[i][j] == 2) {
          brr[i][j] = 0;
          tmp++;
        }
      }
    }

    // 한 칸씩 내리기
    for(int i = n - 2; i >= 0; i--) {
      for(int j = 0; j < m; j++) {
        brr[i + 1][j] = brr[i][j];
        brr[i][j] = 0;
      }
    }

    // 비었나 체크
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        if(brr[i][j]) repeat = 1;
      }
    }
  }

  ans = max(ans, tmp);
}


int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  cin>>n>>m>>d;

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      cin>>arr[i][j];
    }
  }

  for(int i = 0; i < m; i++) {
    for(int j = i + 1; j < m; j++) {
      for(int k = j + 1; k < m; k++) {
        fight(i, j, k);
      }
    }
  }

  cout<<ans;
}

구현 문제이며,  수학적 감을 필요로 한다.

한 자리 수인 1 ~ 9는 9개
두 자리 수인 10 ~ 99는 90개

세 자리 수인 100~999는 900개

...
라는 점을 기반으로 구현해서 푼다.

이런 류의 수학적인 구현력이 많이 부족하다고 느꼈다.

생동성 시험을 하며 병원에서 피 뽑으면서 풀어서 집중하지 못했다. 
결과적으로 오래 걸려서 아쉽다.

/*
https://www.acmicpc.net/problem/1790
백준 1790 수 이어 쓰기 2
*/

#include <iostream>
using namespace std;
int main() {
    long long aa = 0, n,k,temp = 9, l = 1;
    cin>>n>>k;
    while(k > 0) {
        k -= temp * l;
        aa += temp;
        temp *= 10;
        l++;
    }
    temp /= 10;
    k += temp * --l;
    aa -= temp;
    long long num = (k + l - 1)/ l, mod = (k + l - 1) % l;    
    long long m = aa + num;
    if(m > n) cout<<-1;
    else {
        for(long long i = 0; i < l - mod - 1; i++) {
            m /= 10;
        }
        cout<<m % 10;
    }
}

이분탐색 문제입니다.

이 문제에 이분탐색을 어떻게 적용할 수 있을까 엄청 고민했는데, 

일단 정렬하고 생각해봤습니다.

애니메이션을 보는데 걸리는 시간은 보는 애니 중 가장 길이가 긴 것입니다.

따라서 가장 긴 것만 본다고 가정합니다.

또한, 애니메이션은 항상 k개씩 봐야지 가장 많이 볼 수 있습니다.

따라서 k는 고정입니다.

그럼 애니메이션을 몇 개 볼 수 있는지에 대해서 이분탐색을 할 수 있습니다.

7 10 2
2 3 1 4 5 6 7

위와 같이 입력이 들어올 경우

1 2 3 4 5 6 7로 정렬될 겁니다.

이분탐색에서 시작은 1, 끝은 7일 것이며, 중간은 4가 됩니다. 

애니를 4편 봤지만 걸린 총 시간은 6으로, 이는 m값인 10보다 작습니다.

시작점을 중간으로 옮겨주면

시작은 4, 끝은 7, 중간은 5가 됩니다.

애니 5편을 봤을 때 총 걸린 시간은 9로, 이는 m값인 10보다 작습니다.

시작점을 5로, 이에 중간을  6으로 옮기면 총 시간은 12로, m보다 큽니다.

이렇게 이분탐색을 진행하면 0번째부터 시작점까지의 영화를 모두 볼 수 있습니다.

사이드케이스로,

1 1 1
10

과 같은 입력이 들어올 경우, 0번째의 원소 하나만으로도 m값을 넘기기에 이를 신경써야합니다.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long arr[100000],n,m,k,tmp,ans = -1,fir,e,mid, coun;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    for(int i = 0; i < n; i++) cin>>arr[i];
    sort(arr, arr + n);
    
    fir = 0;
    e = n;
    for(int i = 0; i < log2(n); i++) {
        tmp = coun = 0;
        mid = (fir + e) / 2;
        for(int j = mid; j >= 0; j -= k) {
            coun++;
            tmp += arr[j];
        }
        if(tmp <= m) {
            ans = max(ans, coun);
            fir = mid;
        }
        else {
            e = mid;
        }
    }
    
    if(arr[fir] > m) cout<<0; //가장 짧은 애니도 m보다 길 경우
    else cout<<fir + 1;
}

1. N x M 크기의 배열에서 8 x 8 만큼만 잘라내는 법

2. 8 x 8 크기의 배열에서 흰색과 검정색을 교차로 설정하는 법

위의 2가지를 알면 쉽게 구현할 수 있는 브루트포스 문제입니다.

입력이 주어지면 위의 그림만큼 8 x 8만큼 씩만 탐색을 해야하며,

그 내부에서 교차로 선택하는 방법을 알아야 합니다.

    for(int i = 0; i <= n - 8; i++) {
        for(int j = 0; j <= m - 8; j++) {

~~~

~~~

        }

    }

이 부분이 배열에서 8 x 8 만큼씩 탐색하는 방법이고

그 밑의 조건문은 흰색과 검정색을 교차로 놓는 부분입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string s[50];

int main() {
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < n; i++) {
        cin>>s[i];
    }
    int coun, coun2, ans = 100;
    for(int i = 0; i <= n - 8; i++) {
        for(int j = 0; j <= m - 8; j++) { //1번 부분
            coun2 = coun = 0;
            for(int k = 0; k < 8; k++) {
                for(int l = 0; l < 8; l++) {
                    if((k + i) % 2 == 0 && (l + j) % 2 == 0 && s[k + i][l + j] == 'B') coun++; //2번 부분
                    if((k + i) % 2 == 1 && (l + j) % 2 == 1 && s[k + i][l + j] == 'B') coun++;
                    if((k + i) % 2 == 1 && (l + j) % 2 == 0 && s[k + i][l + j] == 'W') coun++;
                    if((k + i) % 2 == 0 && (l + j) % 2 == 1 && s[k + i][l + j] == 'W') coun++;

                    if((k + i) % 2 == 0 && (l + j) % 2 == 0 && s[k + i][l + j] == 'W') coun2++;
                    if((k + i) % 2 == 1 && (l + j) % 2 == 1 && s[k + i][l + j] == 'W') coun2++;
                    if((k + i) % 2 == 1 && (l + j) % 2 == 0 && s[k + i][l + j] == 'B') coun2++;
                    if((k + i) % 2 == 0 && (l + j) % 2 == 1 && s[k + i][l + j] == 'B') coun2++; 
                }
            }
            ans = min({ans, coun, coun2});
        }
    }
    cout<<ans;
}