[백준][Python] 1236번 성 지키기 - 코팩

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

1236번: 성 지키기

 

풀이

처음에는 어떻게 풀지 고민해보았는데, 문제에서 요구하는 바는 행과 열마다 경비원이 하나씩 존재해야한다는 것이다.

어느 n행과 m열이 주어졌을 때 두 직선의 교점에 경비원이 위치한다면 한 경비원으로도 문제에서 원하는 바를 만족시킬 수 있다는 것이다. 그말은 즉슨 가장 긴 직선의 길이만큼 경비원을 배치해준다면 다른 직선의 경비원 문제는 자연스럽게 해결된다는 것이다. 

 

코드

# 1236번 성 지키기
def check(li, length):
    cnt = 0
    for i in range(length):
        if li[i] == False:
            cnt += 1 
    return cnt

n, m = map(int, input().split())
horizon = [False] * n
vertical = [False] * m
grid = [list(input()) for _ in range(n)]
ans = 0

for i in range(n):
    for j in range(m):
        if grid[i][j] == "X":
            horizon[i] = True
            vertical[j] = True

ans = max(check(horizon, n), check(vertical, m))
print(ans)

출력결과