BOJ 28128

현대모비스는 하드웨어 중심의 자동차 부품 회사에서 소프트웨어 중심의 기술 기업으로 거듭나기 위해 소프트웨어 연구개발 역량을 강화하고 있습니다.

현대모비스는 실력 있는 소프트웨어 인재를 양성하고 독려하기 위해 APC의 주최 동아리인 A.N.S.I를 후원하고 있다. 올해 현대모비스는 2023 APC에 참가한 여러분들을 위해 특별상을 준비하였다. 특별상은 추첨을 통해 지급된다. 추첨의 진행은 현빈이가 맡게 되었다.

현대모비스가 준비한 추첨판은 세로의 길이가
$N$, 가로의 길이가
$M$인 격자판이다. 추첨판의 각 격자에는 참가한 학생들의 이름이 적혀있다. 한 학생의 이름이 여러 번 적힐 수도 있다. 현빈이는 직사각형 모양의 또 다른 격자판을 준비하였다. 추첨은 아래의 방법으로 진행한다.

현빈이가 준비한 세로의 길이가
$a$, 가로의 길이가
$b$인 격자판으로 추첨판을 덮는다. 이때, 세로 길이와 가로 길이중 하나는
$1$보다 커야 한다.
추첨판을 덮을 때 추첨판에 부분적으로 걸치는 부분은 없다. 다시 말해 추첨판의 각 격자는 현빈이가 준비한 격자판에 의해 완전하게 덮이거나, 덮이지 않는다.
현빈이가 준비한 격자판으로 덮은 격자에 적힌 여러 이름 중에서 같은 이름이

$\lceil \frac{a\times b+1}{2}\rceil$번 이상 나온다면, 그 이름을 가진 학생은 선물을 받는다.
현대모비스가 준비한 추첨판이 주어졌을 때, 선물을 받을 수 있는 학생들을 알아내 보자.

풀이

격자의 크기는 a, b로, 둘중에 하나는 무조건 1 초과여야 한다.
문제에서 따로 격자의 사이즈를 입력받지 않기 때문에 모든 경우를 생각해 주면 된다.
격자에서 이름이 $\lceil \frac{a\times b+1}{2}\rceil$ 번 나오면 되기 때문에
처음부터 생각해보면 (1, 2)일때는 2번, (2, 2)일때는 3번 (2, 3)일때는 4번으로, 무조건 두개 이상이 붙어있는 모양이 나와야 한다.
추가적으로 (1, 3)같이 한칸 떨어져 있어도 같은 행이나 열에 한칸 떨어진 상태로 2개가 존재한다면 조건을 만족한다.