시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 | 1024 MB | 436 | 109 | 97 | 28.783% |
장기에는 마(馬)와 상(象)이라는 두 가지의 뛰는 기물이 있습니다. 다른 기물들과 다른 이 기물들의 공통점은 가로와 세로로 동시에 움직인다는 것입니다. 따라서 이동 경로를 직선으로 그리게 되면 항상 장기판의 가로 선과 세로 선을 빗겨가게 됩니다. 마(馬)는 가로 혹은 세로 방향으로 한 칸, 다른 방향으로 두 칸 이동하고, 상(象)은 가로 혹은 세로 방향으로 두 칸, 다른 방향으로 세 칸 이동합니다.
마(馬)와 상(象)의 이동 경로 예시, 왼쪽이 마(馬), 오른쪽이 상(象)입니다.
뛰는 기물의 존재 여부는 장기의 후반 흐름을 좌우할 만큼 중요합니다. 오로지 장기가 재밌어서 이런 중책을 천 번도 넘게 맡긴 키파는, 마(馬)와 상(象)에게 뛰는 기물로서의 자부심을 가질 수 있게 특별한 이름을 붙여 주기로 했습니다. 그 이름은, 기물이 각 방향으로 움직이는 칸 수를 앞에 붙여서 $(n, m)$-기물과 같이 정했습니다. 예를 들어 마(馬)는 이제 $(1, 2)$-기물 혹은 $(2, 1)$-기물, 상(象)은 $(2, 3)$-기물 혹은 $(3, 2)$-기물입니다.
이런 이름을 붙이자 키파는 다른 $(N, M)$-기물의 특성 역시 생각해 보기로 했습니다. 이를 위해 장기판은 조금 답답했기 때문에, 무한히 넓은 좌표평면을 생각하기로 했습니다. 곧 키파는 마(馬)와 상(象)과는 다르게 $N$, $M$에 따라 특정 지점에서 다른 지점으로 항상 갈 수 있는 것은 아니라는 것을 깨달았습니다. 예를 들어 $(2, 4)$-기물은 좌표평면의 $(0, 0)$ 위치에서 $(3, 3)$ 위치로 갈 수 없습니다.
키파는 $(N, M)$-기물을 기특히 여겨 선물을 주려고 합니다. 그러나 기물이 너무 멀리 뛰어가 버려서 키파는 기물의 위치를 정확히 알 수 없었고, 대신 격자점 위에 선물을 두고 돌아가기로 했습니다. 기물이 선물이 놓인 격자점을 방문할 수 없게 되는 것이 걱정된 키파는 선물을 많이 가져와서 여러 곳의 격자점에 하나씩 놓기로 했습니다. 기물이 어떤 위치에 있더라도 선물이 놓인 격자점에 방문할 수 있도록 하기 위해, 키파가 준비해야 하는 선물의 최소 개수를 구해 봅시다.
첫째 줄에 음이 아닌 정수 $N$과 $M$이 공백을 사이에 두고 주어집니다. $N$과 $M$은 모두 $10^{9}$보다 작거나 같으며, $N$과 $M$이 모두 $0$인 입력은 주어지지 않습니다.
첫째 줄에 키파가 준비해야 하는 선물의 최소 개수를 출력합니다.
2 4
4
1 2
1
2 3
1
첫 번째 예제의 경우 가로 축과 세로 축에서 모두 홀수 점들과 짝수 점들이 나누어져 있기 때문에 답은 최소 $2 \times 2 = 4$입니다. 선물을 $4$개만 준비해도 된다는 사실을 증명할 수 있습니다.
두 번째 예제의 경우, 예를 들어 $(0, 0) \rightarrow (1, 2) \rightarrow (3, 1) \rightarrow (1, 0)$과 같은 방식으로 한 칸씩 이동할 수 있기 때문에 어떤 위치에든 선물을 하나만 놓아도 기물이 선물을 가져갈 수 있습니다.
세 번째 예제의 경우, 두 번째 예제와 마찬가지로 기물이 한 칸씩 이동할 수 있는 방법이 있습니다. 이 경우는 기물이 한 칸을 이동하는 데 최소 다섯 번의 이동을 필요로 합니다.
University > 서울대학교 > 2021 서울대학교 프로그래밍 경시대회 > Division 2 E번