| [ QuizWit ] in KIDS 글 쓴 이(By): reality (얄이) 날 짜 (Date): 1998년 6월 24일 수요일 오전 11시 12분 16초 제 목(Title): Re: [문제] 1,2,3,...,1998. 이 문제는 좀더 일반화하여 풀도록 하겠습니다. 우선 1 ~ 1998로 되어 있는 값을 1에서 2m까지로 일반화하죠... 이 문제에서 m의 값이 짝수냐, 홀수냐에 따라 풀이가 달라짐을 볼 수 있습니다. 먼저 짝수일 경우는 문제가 말이 되지 않는(?), 즉 풀 수 없는 문제가 됩니다. m이 짝수일 경우를 간단히 설명을 하면, 임의의 한점부터 시작하여, a[i] ( a[1] ~ a[m] )이라고 점에 이름을 붙입니다. 그러면, a[m] 이후부터는 대칭이므로 자연히 a'[i] ( a'[1] ~ a'[m] )이라고 붙일 수 있습니다. 이 때, a[i] + a[i+1] = a'[i] + a'[i+1] (1 <= i <= m-1 인 경우) 로 식이 나오고, 원래의 점과 대칭점의 경계에서 a[m] + a'[1] = a'[m] + a[1] 이라는 식이 나옵니다. 이 식을 풀면, 다음과 같습니다. a[1] + a[2] = a'[1] + a'[2] a[2] + a[3] = a'[2] + a'[3] ...... a[m-1] + a[m] = a'[m-1] + a'[m] 위 식에서 첫번째 식부터 한번 더하고, 빼는 것을 반복하면 (즉, a[i]부분이 홀수로 시작하면 양변을 더하고, 짝수일 경우는 빼면 됩니다.) a[1] + a[m] = a'[1] + a'[m] 이 됩니다. 이 식을 위의 식 a[m] + a'[1] = a'[m] + a[1] 과 연립하면 a[1] = a'[1]이 되어서 문제가 1 ~ 1998까지 전부 사용해야 하는 것이라면 말이 되지 않게 되는 것입니다. 이제 홀수일 때를 풀도록 하죠 (실제 문제도 이렇습니다) 위와 같은 방식으로 식을 세우면, a[i] + a[i+1] = a'[i] + a'[i+1] (1 <= i <= m-1 인 경우) a[m] + a'[1] = a'[m] + a[1] 의 식이 되는 데, 이 때는 두번째 줄의 식이 첫번째에 있는 m-1개의 식과 dependent하게 됩니다. (즉, 두번째 식은 무용지물이 됩니다, 직접 계산해보시면 쉽게 알 수 있을 것입니다) 식을 변형하면, a[i] - a'[i] = - (a[i+1] - a'[i+1]) 이 됩니다. 여기에서 x[i] = a[i] - a'[i] 라고 놓으면, x[i+1] = - x[i]가 되는 것이죠... 따라서, x[i] = (-1)^(i-1) * x[1] 이 됩니다. 우리는 여기에서 절대값만 다를 뿐이라는 사실에서 힌트를 얻어서 원에서 생각을 해보면, 하나 건너 가면서 그 반대쪽에 있는 값과 의 차이가 일정함을 알 수 있습니다. 또, m이 홀수이기 때문에 이렇게 한 바퀴 돌면서 값을 적으면 되죠... (이해가 안 가시면, 1~6사이의 값을 가지고 생각해보십시오) 우리는 한칸씩 건너가면서 m개의 값을 적으면, 그 반대쪽에는 전부 똑같은 차이만큼의 값을 가지는 숫자를 적어야 합니다. 예를 들면, 1에서 6까지의 경우, 4,5,6을 한칸씩 건너면서 적고 각각의 값의 반대쪽에 1,2,3을 적는 경우이죠... (그림) 3 *4 *5 2 1 *6 위의 그림에서 *표가 붙은 것처럼 한 칸씩 건너가면서, 숫자를 쓸 경우 반대편의 숫자와의 차이가 일정해야 합니다. 따라서, 1~2m까지의 숫자를 1~m , (m+1)~2m 까지로 나누어서 둘 중 하나를 한칸씩 건너가면서 배치하면 됩니다. (물론, 그 반대쪽과의 차가 일정해야 하므로 (1, m+1), (2, m+2)...으로 대칭점의 값을 적으면 됩니다) 따라서, k값만큼의 차를 같는 정수의 쌍을 우선 구해야합니다. 총 2m개의 자연수를 2개씩 차가 k가 되도록 묶는 가짓수가 고려되어야 하지요... 여기서, 하나의 자연수가 결정되면, 그것과 차를 k로 가지는 정수는 두가지가 될 수 있습니다. 그러나, 1부터 2m까지이므로, 중간에서 아무렇게나 나누다 보면 양쪽 끝부분(1 , 2m) 쪽에서 제대로 나누어지지 않을 수도 있게 되지요... 예를 들면, m=9, k=3일 때, (5,8)을 묶으면 2는 아무것과도 쌍을 이룰 수 없습니다. 따라서, 앞에서부터(1부터) 묶기 시작하면 2m개의 정수는 처음부터 순서대로 2k개씩이 묶여 나가게 됩니다. 물론, 끝까지 정확하게 묶을 수 있어야하므로 2k은 2m의 약수가 되어야하고, k는 m의 약수가 되어야 합니다. 그리고, 그 각각은 한가지 방법으로 묶이게 됩니다. 따라서, 약수의 가짓수가 더 필요하므로, 약수의 갯수를 편의상 f(m) 이라고 하면, f(m) * (m-1)! 이 되겠지요. 문제는 m= 999 = 3^2 * 111 = 3^3 * 37이므로 (1+3) * (1+1) = 8 이 되므로, 8 * 998! 이 되겠지요... 그럼, 이만... |