| [ QuizWit ] in KIDS 글 쓴 이(By): racer (기사양반) 날 짜 (Date): 1996년04월03일(수) 11시29분51초 KST 제 목(Title): 앗! 벽돌쌓기 틀렸당~~ 위의 게스트님이 거의 맞추셨는데... 일단 2차원에서 생각해보면 m x n 의 경우 서로 소이면 (m + n - 1)개의 벽돌을 통과하고 만일 두수의 최대 공약수(1이 아닌)가 a이라면 (m + n - 1) - (a - 1)개의 벽돌을 통과하죠. l x m x n의 3차원 격자인 경우는 l + (m - 1) + (n - 1)에서 두수의 쌍(lm, mn, nl의 세개의 쌍)의 (최대공약수 - 1)의 갯수만큼 빼주고 나서 (세수의 최대공약수 - 1)만큼을 더해주면 됩니다. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 150 + (324 - 1) + (375 - 1) = 847 150과 324의 최대공약수 : 6 --> 847 - (6 - 1) = 842 150과 375의 최대공약수 : 75 --> 842 - (75 - 1) = 768 324와 375의 최대공약수 : 3 --> 768 - (3 - 1) = 766 세수의 최대공약수 : 3 --> 766 + (3 - 1) = 768 그래서, 답은 768개!! =========================================================== 보충설명 2차원 격자에서는 하나의 선을 통과할때 마다 벽돌이 하나씩 늘게 되는데 만일 가로선과 세로선의 교차점을 통과하게 되면 통과하는 선이 하나 줄게됩니다. 즉, 두개의 선을 통과하지만 벽돌은 하나밖에 안늘게되죠. 통과하는 교차점의 갯수는 최대공약수 보다 하나 적습니다. 3차원에서는 벽돌의 면을 통과할때마다 벽돌이 하나 늘게되는데 만일 벽돌의 모서리를 통과하게되면 2차원과 비슷한 이유로 하나가 줄게됩니다. 그리고 만일 꼭지점을 통과하면 2개가 줄게됩니다. 위의 풀이방법에서 앞뒤, 좌우, 아래위 의 세방향으로 projection을 해서 2차원과 비슷한 방법으로 3차원 문제를 풀때 모서리를 통과할때는 세방향중 한방향에서 2차원 교차점을 지나기 때문에 문제가 없으나 꼭지점을 통과할 때는 세방향 모두에서 교차점을 지나기 때문에 2개가 줄었으나 계산상 3개가 줄게됩니다. 따라서 꼭지점을 통과할 때는 1개를 오히려 더해주어야하지요. 통과하는 꼭지점의 갯수는 세변길이의 최대공약수 - 1 개 입니다. |