"영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다."
말씀하신대로 두면 4행과 5행이 막히지 않습니다.
1236번 - 성 지키기
풀이를 설명하되, 단계별로 힌트를 적는 식으로 적어볼게요. 막힐 때마다 조금씩 공개해서 보시면 좋을 것 같아요. 스포일러 방지를 위해 빈 줄을 좀 넣을게요! 아래로 스크롤해주세요!
모든 행과 열에 한 명 이상의 경비원이 있어야 한다는 뜻은, 비어있는 행과 비어있는 열의 개수가 모두 $0$개여야 함을 의미해요. 비어있는 행과 비어있는 열의 개수를 세어 개수를 알 수 있다면 문제 해결에 도움이 될 수 있을 거에요.
경비병을 한 명 배치했을 때 비어있는 행을 없애기 위해 배치한다면 비어있는 행의 개수는 반드시 $1$ 감소할 것이고, 비어있는 열을 없애기 위해 배치한다면 비어있는 열의 개수는 반드시 $1$ 감소할 거에요.
비어있는 행을 없애기 위해 배치한 경비병이 비어있는 열 중 하나를 동시에 없앨 수 있을까요? 비어있는 행과 비어 있는 열을 합쳐 십자가로 생각한다면요?
비어있는 행 중 하나를 $r$번째 행이라고 하고, 비어있는 열 중 하나를 $c$번째 열이라고 하면, $(r, c)$ 자리는 항상 비어있을 것이고, 여기에 경비병을 배치하면 비어있는 행과 열의 수를 각각 $1$씩 확실하게 감소시킬 수 있어요. 행과 열의 개수를 각각 $2$씩 감소시키는 것은 불가능하니 이것이 최선의 전략일 거에요.
따라서, 비어있는 행이 $r$개, 비어있는 행이 $c$개라면 한 명의 경비병을 배치했을 때 반드시 $r$, $c$를 $1$씩 감소시킬 수 있으니 답은 $r$, $c$ 중 더 큰 값이 돼요. 이중 반복문 등을 이용해 구현할 수 있어요.
댓글을 작성하려면 로그인해야 합니다.
1exxn 1년 전
예제 입력 3
인데
정답은 3이라고 합니다
근데 저거를
이런식으로 2개만 두면 다 막히는거 아닌가요?