[1236번] 성 지키기

문제 출처 :

https://www.acmicpc.net/problem/1236

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

이 문제는 구현을 통해 그리디로 구현 할 수 있다.

어떤 점 x,y에 'X'가 있다면 해당하는 col부분과 row부분을 true로 바꿔준다.

그 후 col과 row에 대해 for문을 돌며 어느 col은 몇군데가 더 경비원이 있어야 하는지 row에는 몇군데에 더 경비원이 있어야하는지 계산해주고 남은 두 값중 max값을 구해준다면 정답을 구할 수 있게 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <iostream> #include <cstdio> #define max(a,b)(a > b ? a : b) using namespace std;   char arr[60][60]; bool col[60]; bool row[60];   int main() {     int n, m;     scanf("%d %d ", &n, &m);       for (int i = 0; i < n; i++)     {         for (int j = 0; j < m; j++)         {             scanf("%c", &arr[i][j]);             if (arr[i][j] == 'X')             {                 col[i] = true;                 row[j] = true;             }         }         getchar();     }       int tn = n;     for (int i = 0; i < n; i++)         if (col[i])             tn--;       int tm = m;     for (int j = 0; j < m; j++)         if (row[j])             tm--;       cout << max(tn, tm);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus