반응형

 이번 시간에는 오랫만에 코딩 테스트가 아닌, 제가 출제한 문제에 대해서 간단하게 해설해 보겠습니다. 사실, 이 문제선린고 대회 문제로 출제하려고 했지만, 모종의 이유로 반려된 문제입니다. 그렇지만, 백준에 낼 가치는 충분히 있다고 판단되어 올리게 되었습니다.이 자리를 빌어, 제 문제를 검수해 주신 분들에게 감사드립니다.

 

 


 아마, 이 블로그의 글들을 유심히 보셨던 분들이라면 제가 키움과 롯데 자이언츠 팬임은 아실 수 있을 겁니다. 이 문제에 나타난 7월 28일을 제가 굳이 언급한 이유는 쓰리런으로 끝내기를 치신 그 분 때문입니다. 각설하고 가희가 9회 말을 보기 위해 풀어야 하는 수학 문제를 보도록 합시다.

 

 

 n개의 수가 최소 공배수가 L이고, 최대 공약수가 G인 가짓수를 구해야 하는 게 목표입니다. 보기만 해도 토가 나오는데요. 일단, 가짓수가 0인 경우부터 생각해 봅시다. L이 G의 배수가 아니면 어떨까요? a(1), ... , a(n)의 최대 공약수가 G이고, 최소 공배수가 L이라는 것은 a(1), ... , a(n)의 배수가 L이라는 이야기입니다. 그리고 a(1), ... , a(n)의 약수가 G라는 의미입니다. a의 배수가 L이고, a의 약수가 G인데, L이 G의 배수가 아니래요. 이런 경우는 없어요. 그러니 L이 G로 떨어지지 않으면 0이라고 하시면 됩니다.

 

 문제는 L이 G로 떨어지는 경우입니다. 어떻게 해야 할까요? 몇 가지 케이스를 들면서 규칙을 먼저 찾아보겠습니다.

 

 

 n이 3이고, 배열에 들어가 있는 수가 32, 16, 16이라고 해 보겠습니다. L은 32이고 G는 16입니다. 어떻게 나왔을까요? 32는 2^5이고 16은 2^4입니다. 이것에 착안해 보겠습니다.

 

 

 위 그림은 2의 지수만 분리한 것입니다. 1번째 인덱스에 있는 것은 5, 2번째와 3번째에 있는 것은 4입니다. L이 32이고 G가 16이래요. L은 2^5인데요. 지수 부분만 따면 5입니다. 이 배열 내에 있는 최댓값을 의미합니다. G는 2^4인데요. 이 배열 내에 있는 최솟값을 의미합니다. 이제 소인수가 2개만 나오는 케이스입니다.

 

 

 최대 공약수 G와 최소 공배수 L은 각각 6, 36입니다. 이 값이 어떻게 나왔을까요? 이들의 소인수는 2와 3입니다.

 

 

그림으로 표현해 볼까요? 위 그림에서 1번째 표 앞에 2가 있고, 2번째 표 앞에 3이 있어요. 이는 소인수를 의미합니다. 소인수 2 옆에는 2, 1, 2가 써져 있는 표가 있고, 3 옆에는 1, 2, 1이 써져 있는 표가 있습니다. 이는 각각 12, 18, 12가 소인수 2가 2, 1, 2개 있는 것을 의미해요. 소인수 3은 1, 2, 1개 있고요.

 

 최소 공배수 36을 소인수 분해 하면 2^2 x 3^2인데요. 이는 소인수 2와 3이 2개 있음을 의미합니다. 이 2는 무엇을 의미할까요? 2, 1, 2가 써져 있는 표에서의 최댓값 2, 1, 2, 1이 써져있는 표에서의 최댓값 2를 의미합니다. 최대 공약수 G 값은 6이였는데요. 6을 소인수 분해 하면 2 x 3입니다. 소인수 2와 3이 각각 1개씩 있습니다. 이 1과 위에 있는 표, 아래에 있는 표의 최솟값과 관련이 있는 거 같지 않나요?

 

 


 여기까지 파악하셨다면, 이런 문제로 변환되었음을 알 수 있습니다.

 

 

 이 배열에서 최댓값이 a이고 최솟값이 b가 되도록 채우는 가짓수는 몇 가지인가? 이걸 깡으로 생각하기에는 굉장히 어렵습니다. 대신에, 이런 문제로 바꿔서 생각해 보면 어떨까요? 위 배열에서 a보다 크거나 같고, b보다 작거나 같은 수를 채우는 경우는 몇 가지인가? 이 문제는 굉장히 쉽습니다.

 

 

 그냥 각 칸마다 a, ... , b 중 하나를 뽑으면 되기 때문입니다. 총 n개의 칸이 있기 때문에 (b-a+1)^n이 됩니다. 문제는 이것입니다. 최솟값이 a이고 최댓값이 b여야 한다는 것입니다. 이 말인 즉슨, 각 칸마다 a ~ b 중 하나를 뽑되, a가 최소한 하나 이상 들어가고, b가 최소한 하나 이상 들어가야 한다는 것입니다. a가 최소한 하나 이상 들어가야 한다는 조건을 A, b가 최소한 하나 이상 들어가야 하는 조건을 B라 두겠습니다.

 

 

 노란색으로 칠한 부분의 가짓수를 구하는 것이 목적입니다. 전체 부분인 U는 n개의 칸에 a ~ b까지의 수를 채워넣는 상황이라고 하겠습니다. A는 a가 최소한 하나 이상 있는 것이고, B는 b가 최소한 하나 이상 있는 것입니다. not A는 무엇인가요? a가 모두 없는 것입니다. not B는요? b가 모두 없는 것입니다. 최소 하나 이상의 부정은 모두 아니다인 것 정도는 간파하시면 좋습니다.

 

 n개의 칸에 a ~ b까지 수를 채워 넣어야 하는데 a가 모두 없다? 뭘까요? n개의 칸에 (a+1) ~ b까지의 수를 채워야 하는 가짓수를 의미합니다.

 

 

 이 상황을 그림으로 나타내면 위와 같습니다. 가짓수는 (b-a)^n입니다.

 

 

 벤다이어로 나타내면 이렇겠네요. 다음에 B가 아니려면 b가 하나도 없어야 합니다. a ~ b 중에 하나를 아무렇게나 택해서 n개의 칸에 채울 건데, b가 하나도 없어야 한대요. 그러면 상황이 어떻게 그려질까요?

 

 

 상황을 요래 그릴 수 있습니다. 가짓수는 (b-a)^n이 됩니다.

 

 

 벤다이어로 나타내면 이래 됩니다. 그러면, (b-a+1)^n에서 (b-a)^n, (b-a)^n을 빼면 되겠군요? 그런데 여기서 함정이 하나 있습니다. not A이면서 notB인 경우가 중복해서 빠졌다는 것입니다. 뭘까요? a ~ b까지 수를 아무렇게나 택해서 n개의 칸에 채울 건데요. a도 하나도 없어야 하고, b도 하나도 없어야 해요. 이 경우입니다.

 

 

 a+1부터 b-1까지 아무렇게나 택하면 해당 조건을 만족할 수 있어요. 따라서 (b-a-1)^n을 더해야 합니다.

 

 


 n개의 칸에 [a, b]에 속하는 정수를 아무렇게나 배치할 것인데 최솟값이 a이고 최댓값이 b인 경우를 구했습니다. 이것을 문제에 어떻게 적용시키면 될까요? 소인수별로 저 상황이 독립적으로 들어갑니다. 따라서, L이 소인수 k를 b개, G가 소인수 k를 a개 가지고 있다면, 최솟값이 a이고 최댓값이 b인 가짓수인 상황 하나로 대응시키면 됩니다. L이 소인수 k'을 b'개, G가 소인수 k를 a'개 가지고 잇다면, 최솟값이 a'이고 최댓값이  b'인 가짓수인 상황 하나로 대응시키면 됩니다.

 

 이들은 별개의 사건입니다. 왜? 소인수 k의 갯수가 소인수 k'의 갯수에 영향을 끼치지 않기 때문입니다. 문제에서는 n개의 수의 최대공약수가 G이고 최소 공배수가 L인 가짓수를 구하라고 했으므로, 상황은 요렇게 그려지게 됩니다.

 

 

 이제 곱사건을 적용시키면 됩니다.

반응형

댓글을 달아 주세요