Codeforce Round #771 (Div. 2) 풀이

대회 링크 : https://codeforces.com/contest/1638

 

A번 문제 : Reverse

순열을 한번만 뒤집어 사전순으로 가장 빠르게 만들어야 하는 문제입니다.

순열과 사전순이라는 특성을 이용하여 입력받은 순열을 순차탐색하면서 \(p[i] != i\) 인 최초의 지점을 찾고 \(i\)를 값으로 가지는 순열의 위치를 찾아 두 개의 지점을 양 끝점으로 하여 reverse 연산을 해주면 사전순으로 가장 빠른 순열을 만들어줄 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int t, n, p[505];

int main() {
   scanf("%d", &t);
   while(t--) {
      scanf("%d", &n);
      int fir = 0; //p[i] != i인 최초의 지점
      for (int i = 1; i<= n; i++) scanf("%d", &p[i]);
      for (int i = 1; i <= n; i++) {
         if(p[i] != i) {fir = i; break;}
      }
      for (int i = 1; i <= n; i++) {
         if(p[i] == fir) {reverse(p+fir, p+i+1); break;}
      }
      for (int i = 1; i <= n; i++) printf("%d ", p[i]);
      printf("\n");
   }
   return 0;
}

 

B번 문제 : Odd Swap Sort

\(a[i] + a[i+1]\)이 홀수일때만 swap이 가능합니다. 따라서 홀수+홀수, 짝수+짝수인 경우에는 위치를 바꾸어 줄 수 없습니다. 이 관찰을 이용하여 입력받은 배열을 짝수/홀수로 나누어 탐색하면서 각각이 오름차순으로 정렬되어있는지 확인하면 됩니다. 이때, 짝수/홀수가 오름차순으로 정렬되어 있지 않다면 Swap Sort를 해주는 과정에서 두 짝수/홀수의 위치를 바꾸어줄 수 없기때문에 정렬이 불가능하다는 사실을 알 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int t, n, a[101010];
int main() {
   scanf("%d", &t);
   while(t--) {
      int mo = 0, me = 0, chk = 0; //max odd, max even
      scanf("%d", &n);
      for (int i = 1; i <= n; i++) {
         scanf("%d", &a[i]);
         if(a[i]%2 == 0) {
            if(me > a[i]) chk = 1;
            else me = a[i];
         }
         else {
            if(mo > a[i]) chk = 1;
            else mo = a[i];
         }
      }
      if(chk == 1) printf("NO\n");
      else printf("YES\n");
   }
   return 0;
}

 

C번 문제 : Inversion Graph

순열을 순차탐색하면서 최댓값을 갱신해주는 과정을 거치게 됩니다. 만약 최댓값이 갱신되지 않는다(\(max>p[i]\))라면 \(p[i]\)를 \(max\)의 component라고 볼 수 있습니다.

이때 최댓값과 i가 같다면 \([1, i]\) 범위의 connection이 적절히 있을 것이고, 남은 범위인 \([i+1, n]\)의 모든 값이 현재의 최댓값보다 크기 때문에 \([1, i]\)와 \([i+1, n]\)은 최소 독립적인 두 개의 component를 이룬다는 사실을 알 수 있습니다.

이 특징을 이용하여 최댓값을 갱신시켜주면서 최댓값과 i가 같을 때 component의 개수를 1씩 더해주면 문제를 해결할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int t, n, p[101010];

int main() {
   scanf("%d", &t);
   while(t--) {
      int maxx = 0, ans = 0;
      scanf("%d", &n);
      for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
      for (int i = 1; i <= n; i++) {
         maxx = max(maxx, p[i]);
         if(maxx == i) ans++;
      }
      printf("%d\n", ans);
   }
   return 0;
}

 

D번 문제 : Big Brush

D번 문제는 마지막으로 칠한 페인트부터 거꾸로 찾아가는 방식입니다.

먼저, 간단한 관찰을 통해 페인트를 아무리 많이 덧칠하더라도 마지막으로 칠한 페인트는 덧칠되지 않고 2x2에서 single color를 가지고 있을 것입니다. 이것을 시작점으로써 queue에 넣어줍니다.

시작점으로 잡은 2x2의 페인트를 제거해준다면, 제거한 위치에는 어떤 페인트 색이든 들어갈 수 있는 특별한 위치라는 사실을 알 수 있습니다. 따라서, 이 특별한 위치 주변을 탐색하며 single color로 이루어진 2x2 크기를 찾는다면 다시 queue에 넣어줍니다.

이를 반복적으로 실행하면 BFS와 유사한 방식으로 문제를 해결해 줄 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, a[1010][1010] = {{0}}, tmp;
vector<pair<int, pair<int, int>>> ans;
queue<pair<int, pair<int, int>>> q;

bool chk_4(int sx, int sy, int num) {
   for (int i = sx; i <= sx+1; i++) {
      for (int j = sy; j <= sy+1; j++) {
         if(a[i][j] != num && a[i][j] > 0) {
            if(num == -1) num = a[i][j];
            else return false;
         }
      }
   }
   if(num == -1) return false;
   for (int i = sx; i <= sx+1; i++)
      for (int j = sy; j <= sy+1; j++) a[i][j] = -1;
   tmp = num;
   return true;
}

int main() {
   scanf("%d %d", &n, &m);
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
   }
   //finding the 2x2 points
   for (int i = 1; i < n; i++) {
      for (int j = 1; j < m; j++) {
         if(chk_4(i, j, a[i][j]) == true) q.push(make_pair(i, make_pair(j, tmp)));
      }
   }
   while(1) {
      int s = q.size();
      while(s--) {
         int sx = q.front().first, sy = q.front().second.first, num = q.front().second.second;
         q.pop();
         ans.push_back(make_pair(sx, make_pair(sy, num)));
         for (int i = sx-1; i <= sx+1; i++) {
            for (int j = sy-1; j <= sy+1; j++) {
               if(i < 1 || j < 1 || i >= n || j >= m) continue;
               if(chk_4(i, j, a[i][j]) == true) q.push(make_pair(i, make_pair(j, tmp)));
            }
         }
      }
      if(q.empty()) break;
   }
   int chk = 0;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) if(a[i][j] > 0) chk = 1;
   }
   if(chk == 1) {printf("-1"); return 0;}
   int s = ans.size();
   printf("%d\n", s);
   for (int i = s-1; i >= 0; i--) printf("%d %d %d\n", ans[i].first, ans[i].second.first, ans[i].second.second);
   return 0;
}