[BOJ 24040] 백준 24040번 - 예쁜 케이크

December 31, 2021

1. 문제

$24040$. 예쁜 케이크 (Good Bye, BOJ 2021! B번)

백준 24040번 - 예쁜 케이크 (https://www.acmicpc.net/problem/24040)

가로 $a$, 세로 $b$의 직육면체라고 가정할 때 $(a \times b = N)$, 예쁜 케이크를 만들려면 이 직육면체에서 띠를 두르는 부분의 길이 즉 $2 \times (a + b)$가 $3$으로 나누어 떨어져야 한다.

$2 \times (a + b)$가 $3$의 배수가 되는 것은 $(a + b)$가 $3$의 배수인 것과 동일하다. $(a + b)$가 $3$의 배수가 되려면 다음과 같은 조건 중 하나를 만족하면 된다.

$a $ $= 3 \times x,\, b $ $= 3 \times y \rightarrow a + b $ $= 3x + 3y $ $= 3(x+y)$
$a $ $= 3 \times x + 1,\, b $ $= 3 \times y + 2 \rightarrow a + b $ $= 3x + 1 + 3y + 2 $ $= 3x + 3y + 3 $ $= 3(x+y+1)$

$1$의 경우 $\rightarrow N $ $= a \times b $ $= 3x \times 3y $ $= 9xy $ $= 9 \times (xy) $ $\rightarrow N$이 $9$의 배수
$2$의 경우 $\rightarrow N $ $= a \times b $ $= (3x+1) \times (3y+2) $ $= 9xy + 6x + 3y + 2 $ $= 3(3xy+2x+y) + 2 $ $\rightarrow N$이 $3z+2$의 형태

따라서 $2 \times (a + b)$가 $3$의 배수가 되려면, $N$이 $9$의 배수이거나 $3z+2$ ($3$으로 나누었을 때, 나머지가 $2$)의 형태이면 된다.