Codeforces Round #749(Div. 1 + Div. 2)

제주도 여행을 다녀오고 오랜만에 진행한 Codeforces Round.

러시아 고등학생들의 올림피아드 대회인 Technocup의 예선전 문제를 그대로 가져와 Round로 진행했다.

그래서인지 A, B, C, D, E, F, G, H, I 총 9문제로 기존 Round들과 차이가 있다.

 

https://codeforces.com/contest/1586/problem/A

https://codeforces.com/contest/1586/problem/A

주어진 양의 정수들을 최대한 많이 사용해서 선택한 정수들의 총합이 합성수가 되게 만드는 문제. (합성수는 약수가 3개 이상인 수)

A문제는 무조건 단순한 방법이 있다고 가정하고 접근해야 하는데 오랜만에 라운드를 진행했더니 감이 떨어졌는지 주어진 정수를 모두 더한 뒤 BFS로 하나씩 빼면서 총합이 합성수인지 확인하는 방법을 쓰려했었다.

그런데 아무리 생각해도 A문제를 그런 식으로 냈을 것 같지 않아서 코드 작성을 미루고 다른 방법을 더 생각해봤다.

그러다 짝수 홀수로 접근해야겠다는 생각이 들었고 단순한 방법을 찾을 수 있었다.

주어지는 양의 정수는 중복되지 않고 3개 이상이기 때문에 주어진 모든 정수의 합은 2보다 크기 때문에 총합이 짝수면 무조건 합성수. 그렇기 때문에 모든 정수의 총합이 짝수면 모든 정수를 사용하면 된다.

총합이 홀수인 경우에는 합성수인지 아닌지 확인을 해야 한다. 만약 소수라면 정수 중 홀수를 하나 찾아 빼주면 그 수는 무조건 짝수가 되고 합성수가 된다. 주어진 정수가 모두 짝수면 총합도 짝수이기 때문에 총합이 홀수면 홀수인 정수는 무조건 존재한다.

 

https://codeforces.com/contest/1586/problem/B

https://codeforces.com/contest/1586/problem/B

m개의 제약사항이 주어질 때 제약사항들을 모두 만족하는 n개의 노드로 이루어진 트리를 만드는 문제.

제약사항은 세 정수가 a b c 형태의 주어지고 a 노드와 c 노드를 잇는 경로 사이에 b 노드가 존재하지 않아야 한다는 것을 의미한다.

처음에는 일자로 노드들을 나열하고 제약사항에 맞춰서 정렬을 하는 방법으로 접근하려 했으나 앞선 제약사항과 관련되어 있는 숫자들이 포함되어 있는 제약사항이 후에 나오면 모두 만족시키기 어려워 다른 방법을 찾아야 했다.

결국 문제를 해결 못하고 다음 문제로 넘어갔었는데 해설을 보니 매우 단순한 문제였다. 문제가 9개인걸 감안하면 이 문제 역시 단순하게 생각했어야 했다.

Input 조건에서 m(제약사항의 개수) < n(노드의 개수) 가 주어진다는 것이 핵심이다. 즉 노드 중 하나는 제약사항의 중간에 해당하는 b에 해당하지 않는다는 것이다.

4번 노드가 제약 사항의 b에 해당하지 않는다고 할 때, 그림과 같이 제약사항에 해당하지 않는 노드 중 하나를 중앙에 놓고 나머지를 중앙 노드에 연결하면 모든 제약사항을 만족한다는 것을 직관적으로 알 수 있다.

https://codeforces.com/contest/1586/problem/C

https://codeforces.com/contest/1586/problem/C

문제 C는 문제 해결 조건들은 파악했지만 시간 초과를 해결하지 못한 문제.

n행 m열의 격자에 채워져 있는 경우에는 X, 비워져 있는 경우에는 .으로 표현한다.

a행 b열에서 시작해 위 또는 왼쪽 방향으로 이동해 격자 밖으로 나갈 수 있는 칸을 Exitable이라고 한다. a행 b열이 채워져 있는 경우에는 나갈 수 없는 것으로 판단한다.

n행 m열의 격자에서 세로로 잘라 부분 격자를 만들어 n행 x열 격자를 만들고 각 행 열의 Exitable 여부로 격자를 E 와 N으로 치환했을 때, 치환한 격자를 보고 다시 X .로 치환할 때 원래의 격자모양으로만 복원이 가능한 경우는 YES를 출력하고 다른 모양의 격자로도 치환되면 NO를 출력한다.

그림을 보면 이해가 쉽다.

초록색의 경우는 원본 격자의 2열부터 4열까지 가져와 만든 부분격자.  E와 N으로 만든 격자에서 다시 . X 격자로 만들 때 한 가지 방법밖에 없다. 이 경우에는 YES를 출력.

빨간색의 경우에는 다시 치환했을 때 기존의 부분 격자와 다른 모양으로 만들 수 있다. 이 경우에는 NO를 출력한다.

NO가 되는 기준은 부분 격자에 . -> N으로 치환되는 칸이 있는가 라는 것을 알 수 있다. 역으로 치환하는 과정에서 1:1로 치환된다는 것은 E는 무조건 .으로 N은 무조건 X로 치환할 수 있는 경우기 때문에.

. -> N이 되는 경우는 바로 위와 왼쪽이 막혀있는 경우. 정확하게는 그림의 빨간색 경우처럼 바로 위가 막혀있지 않더라도 왼쪽이 다 막혀있다면 . -> N이 될 수 있다 하지만 열 단위로 자르기 때문에 하나의 . -> N 경우가 있으면 NO가 되기 때문에 빨간색 경우에서 2열 2행의 칸만 체크하면 된다.

여기까지는 생각을 했으나 부분 격자의 쿼리들이 주어질 때 빠르게 YES인지 NO인지 판별하는 방법을 찾지 못했었다.

   int[] numBad = new int[m+1]; 
   int total = 0;
   for(int j = 0; j < m-1; j++)
   {
      for(int i = 1; i< n; i++)
      {
         if(grid[i][j] == 1 && grid[i-1][j+1] == 1)
         {
            total++;
         }
      }
      numBad[j+1] = total;
   }
   numBad[m] = total;
   
   int q;
   scanf("%d", &q);
   for(int i = 0; i < q; i++)
   {
   	  int a, b;
   	  scanf("%d %d", &a, &b);
      if(numBad[b]-numBad[a] == 0)
      {
         printf("yes\n");
      }
      else
      {
         printf("no\n");
      }
   }

해설에서 사용한 방법은 열 왼쪽부터 오른쪽까지 누적합 값을 배열에 저장하고 둘의 누적합 값을 뺏을 때 0이면 사이에 있는 열에 . -> x 경우가 하나도 없었음을 한 번의 연산으로 알 수 있다.

누적합을 저장해서 비교하는 방식은 종종 활용하는 경우가 나올 것 같으니 기억해야겠다.