타일 도로망의 수의 곱

[출제의도] 소인수분해를 이용하여 주어진 조건을 만족시키는 수의 합을 추론한다. $382200$을 소인수분해하면 $382200$$= 2 ^{3} \times 3 \times 5 ^{2} \times 7 ^{2} \times 13$ 이므로 $2$가 $3$번, $3$이 $1$번, $5$가 $2$번, $7$이 $2$번, $13$이 한 번 곱해진다. 따라서 지나갈 수 있는 타일의 최대 개수는 $9$개이다. 또한 주어진 도로망에서 $9$, $11$, $22$, $17$, $19$가 적힌 타일은 지날 수 없다. 따라서 지날 수 있는 타일은 그림과 같다.

$382200$에서 소인수 $3$과 $13$은 한 번씩만 곱해지므로 $3$의 배수인 $3$ 또는 $6$이 적힌 타일 중 하나를 한 번, $13$이 적힌 타일을 한 번 지나야 한다. 따라서 지날 수 있는 경로는 다음과 같다. (ⅰ) 처음에 $2$가 적힌 타일을 지나는 경우 반드시 $3$이 적힌 타일을 거쳐서 $13$이 적힌 타일을 지나야 한다. 이 경우 $9$개 이하의 타일을 지나는 경로는 없으므로 조건을 만족하는 경로는 없다. (ⅱ) 처음에 $6$이 적힌 타일을 지나는 경우 두 번째로 지나는 타일에 적힌 수는 $7$이고 $3$과 $6$이 적힌 타일은 동시에 지날 수 없으므로 세 번째로 지나는 타일은 $10$이다. $6$→$7$→$10$→$7$→$\cdots$로 이동하는 경우 $\mathrm{B}$ 지점으로 이동하는 모든 경로는 $7$을 추가로 한 번 이상 지나게 되므로 $7$이 세 번 이상 곱해져서 조건을 만족하는 경로는 없다. $6$→$7$→$10$→$5$→$\cdots$로 이동하는 경우 $\mathrm{B}$ 지점으로 이동하는 모든 경로는 $5$을 추가로 한 번 이상 지나게 되므로 $5$가 세 번 이상 곱해져서 조건을 만족하는 경로는 없다. $6$→$7$→$10$→$2$로 이동하는 경우 계속하여 $6$→$7$→$10$→$2$→$7$→$13$→$5$로 이동해야 한다. 이때 지나간 타일에 적힌 모든 수의 곱은 다음과 같다. $6 \times 7 \times 10 \times 2 \times 7 \times 13 \times 5$$= 2 ^{3} \times 3 \times 5 ^{2} \times 7 ^{2} \times 13$ 이 곱은 문제의 조건을 만족시킨다. 따라서 지나간 타일에 적힌 모든 수의 합은 다음과 같다. $6 + 7 + 10 + 2 + 7 + 13 + 5$$= 50$ (ⅲ) 처음에 $4$가 적힌 타일을 지나는 경우 $3$ 또는 $6$이 적힌 타일 중 하나를 한 번, $13$이 적힌 타일을 한 번 지나는 경로는 존재하지 않으므로 주어진 조건을 만족하는 경로는 없다. (ⅰ), (ⅱ), (ⅲ)에서 구하는 합은 $50$이다. [다른 풀이] $382200$을 소인수분해하면 $382200$$= 2 ^{3} \times 3 \times 5 ^{2} \times 7 ^{2} \times 13$ 이므로 $2$가 $3$번, $3$이 $1$번, $5$가 $2$번, $7$이 $2$번, $13$이 $1$번 곱해진다. 또한 주어진 도로망에서 $9$, $11$, $22$, $17$, $19$가 적힌 타일은 지날 수 없다. 따라서 지날 수 있는 타일은 다음 그림과 같다.

$\mathrm{B}$에서부터 지나온 자리를 거꾸로 찾아오면 맨 아래 줄의 $13$은 지날 수 없으므로 맨 윗줄의 $13$을 지나야한다. 따라서 경로의 마지막은 $7$→$13$→$5$이다. 이후 $6$ 또는 $3$을 지나야 하므로 세 번째 줄의 $7$을 지나야 하고, $7$을 지나기 위해서는 그 위의 $10$도 지나야 한다.

이미 $5$와 $10$을 지났으므로 $5$는 더 이상 지날 수 없다. 따라서 두 번째 줄의 $2$를 지나야 한다.

거쳐야 할 타일의 남은 수의 곱은 $6$뿐이므로 가능한 경로는 $6$을 지나는 경우뿐이다. 따라서 아래 그림과 같이 동그라미가 그려진 수를 따라가야 한다.

따라서 지나간 타일에 적힌 모든 수의 합은 다음과 같다. $6 + 7 + 10 + 2 + 7 + 13 + 5$$= 50$