1236 - 성 지키기

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

모든 행과 열에 1명 이상의 경비원을 배치한다.

채워야 할 가로의 수를 R, 세로의 수 C라 한다면 min(R, C) 만큼의 경비원은 겹치는 것이 최소이다. (1명으로 2개의 겹치는 공간을 해결하는 것이 불필요한 경비원을 줄이기 때문)

그럼 위의 경비원으로 min(R, C) 만큼 채웠고, 남은 빈 칸(또는 줄)을 채우는 것이 문제인데, 어딜 가건 이미 줄(또는 칸)을 다 채웠기때문에 남은 빈 칸(또는 줄)에 아무렇게나 채우면 된다.

답은 R+C-min(R, C)

데이터 만드는 게 오래걸려서 파이선으로 만들어봤다.

랜덤 데이터 생성 소스 첨부

import random
N, M = random.randrange(1,25), random.randrange(1,25)
print N, M
for _ in range(N):
 s = ""
 for _ in range(M):
  s += "1" if random.randrange(1,10)==1 else "."
 print s

#include <cstdio>
#include <algorithm>
int main(){
    int i, j, n, m;
    scanf("%d %d ", &n, &m);
    char s[50][51];
    for(i=0; i<n; ++i) scanf("%s ", s[i]);
    int r=0, c=0;
    for(i=0; i<n; ++i){
        bool space = true;
        for(j=0; j<m && space; ++j) space &= s[i][j]=='.';
        r += space;
    }
    for(i=0; i<m; ++i){
        bool space = true;
        for(j=0; j<n && space; ++j) space &= s[j][i]=='.';
        c += space;
    }
    printf("%d", r+c-std::min(r,c));
    return 0;
}