토탐정 골랜디 돌리다가 이 문제를 마주했습니다. 30분 정도 고민하다가 모르겠어서 에디토리얼(솔브드 디스코드에 있습니다)을 봤는데, 해설의 풀이가 참 그럴 듯 하면서 충분히 큰 임의의 N에 대한 증명이 참 어렵더라구요... 해설의 정당성 증명을 몇 번 시도해보다가, 좀 더 간단한 (그리고 증명도 더 단순한) 다른 구성 방법을 찾아서 이곳에 글로 남기기로 했습니다.
N을 연속으로 배치한 후, 사이사이에 1을 적절하게 위치시키는 것이 기본 아이디어입니다.
수열에서 연속된 "N-블럭"의 개수를 k, 그리고 i번째 블럭의 크기를 a_i로 표기하겠습니다.
예를 들어서, {1 N N N 1 N N 1 1 1 N N N N}과 같은 수열에서 k는 3이고, a_i의 값들은 각각 3, 2, 4입니다.
그렇다면, 각 "N-블럭"에서 만들 수 있는 구간의 개수는 1 + 2 + 3 + ... + a_i = a_i(a_i+1)/2입니다. 편의상 이 식을 f(x) = x(x+1)/2를 사용하여 f(a_i)로 표현하겠습니다.
만일, N = f(a_1) + f(a_2) + f(a_3) + ... + f(a_k)이고, N >= a_1 + a_2 + a_3 + ... + a_k + (k-1)이라면, 조건을 만족하는 수열을 구성할 수 있음을 알 수 있습니다. (여기서 k-1은 k개의 "N-블럭"을 구분하기 위해 최소로 필요한 1의 개수입니다.)
f(x)의 성질을 사용하여 위 조건을 만족시키는 수열을 구성하겠습니다. 성질들은 다음과 같습니다.
x = 3일 때, f(x) = x + 3이다.
x = 2일 때, f(x) = x + 1이다.
x = 1일 때, f(x) = x이다.
1) N이 3의 배수라면, 모든 i에 대하여 a_i를 2로 정하면 됩니다. 그러면, f(a_i) = 3이고, f(a_i) = a_i + 1이므로, 다음과 같은 식이 성립합니다.
따라서 {N N N 1 N N 1 N N 1 N N 1 ... N N 1 N 1 N 1}과 같은 수열을 구성하면 됩니다 (N N N 1로 시작, 이후 N N 1을 floor(N/3)-2번 반복, 마지막 부분은 N 1 N 1).
위와 같은 구성을 할 수 없는 경우는 N=2와 N=5입니다. f(a_1) = 6이므로, N을 초과하기 때문입니다.
이와 같은 경우는, 수열의 길이가 작기 때문에, 모든 경우를 전부 탐색해볼 수 있습니다. 실제로 브루트포싱을 이용하여 가능한 수열을 탐색해보면, N=2 또는 N=5일 때 조건을 만족시키는 수열이 단 한개도 존재하지 않음을 알 수 있습니다. 따라서 예외 케이스인 N=2, N=5를 먼저 처리해주고, 이외 경우들은 위와 같은 방법으로 수열을 구성하면 됩니다.
N을 3가지 경우로 나누어, N=2와 N=5를 제외한 모든 N에 대하여 조건을 만족시키는 수열이 존재함을 보였습니다.
2시간을 투자해도 보이지 않던 방법이 운동하고 오니까 30분만에 보이는군요... 이런 거 잘하려면 운동은 필수인가 봅니다. 새로운 구성 방안을 생각해낸 것과는 별개로, 에디토리얼에서 설명한 방법의 정당성은 아직도 증명을 못하겠습니다. 아시는 분 있으면 좀 알려주세요...
kcits970 1년 전 1
토탐정 골랜디 돌리다가 이 문제를 마주했습니다. 30분 정도 고민하다가 모르겠어서 에디토리얼(솔브드 디스코드에 있습니다)을 봤는데, 해설의 풀이가 참 그럴 듯 하면서 충분히 큰 임의의 N에 대한 증명이 참 어렵더라구요... 해설의 정당성 증명을 몇 번 시도해보다가, 좀 더 간단한 (그리고 증명도 더 단순한) 다른 구성 방법을 찾아서 이곳에 글로 남기기로 했습니다.
N을 연속으로 배치한 후, 사이사이에 1을 적절하게 위치시키는 것이 기본 아이디어입니다.
수열에서 연속된 "N-블럭"의 개수를 k, 그리고 i번째 블럭의 크기를 a_i로 표기하겠습니다.
예를 들어서, {1 N N N 1 N N 1 1 1 N N N N}과 같은 수열에서 k는 3이고, a_i의 값들은 각각 3, 2, 4입니다.
그렇다면, 각 "N-블럭"에서 만들 수 있는 구간의 개수는 1 + 2 + 3 + ... + a_i = a_i(a_i+1)/2입니다. 편의상 이 식을 f(x) = x(x+1)/2를 사용하여 f(a_i)로 표현하겠습니다.
만일, N = f(a_1) + f(a_2) + f(a_3) + ... + f(a_k)이고, N >= a_1 + a_2 + a_3 + ... + a_k + (k-1)이라면, 조건을 만족하는 수열을 구성할 수 있음을 알 수 있습니다. (여기서 k-1은 k개의 "N-블럭"을 구분하기 위해 최소로 필요한 1의 개수입니다.)
f(x)의 성질을 사용하여 위 조건을 만족시키는 수열을 구성하겠습니다. 성질들은 다음과 같습니다.
x = 3일 때, f(x) = x + 3이다.
x = 2일 때, f(x) = x + 1이다.
x = 1일 때, f(x) = x이다.
1) N이 3의 배수라면, 모든 i에 대하여 a_i를 2로 정하면 됩니다. 그러면, f(a_i) = 3이고, f(a_i) = a_i + 1이므로, 다음과 같은 식이 성립합니다.
N = f(a_1) + f(a_2) + f(a_3) + ... + f(a_k)
= (a_1 + 1) + (a_2 + 1) + (a_3 + 1) + ... + (a_k + 1)
= a_1 + a_2 + a_3 + ... + a_k + k
>= a_1 + a_2 + a_3 + ... + a_k + (k-1)
따라서 {N N 1 N N 1 N N 1 N N 1 N N 1 ...}와 같은 수열을 구성하면 됩니다 (N N 1이 N/3번 반복).
2) N을 3으로 나눈 나머지가 1이라면, 1 <= i <= k-1인 모든 i에 대하여 a_i를 2, 그리고 마지막 원소인 a_k는 1로 정하면 됩니다.
앞선 경우와 비슷한 식을 이용하여 조건을 만족시킴을 증명할 수 있습니다.
N = f(a_1) + f(a_2) + f(a_3) + ... + f(a_k)
= (a_1 + 1) + (a_2 + 1) + (a_3 + 1) + ... + (a_{k-1} + 1) + a_k
= a_1 + a_2 + a_3 + ... + a_k + (k-1)
따라서 {N N 1 N N 1 N N 1 ... N N 1 N}와 같은 수열을 구성하면 됩니다 (N N 1이 floor(N/3)번 반복, 마지막 원소는 N).
여기서 N=1은 예외 케이스입니다. a_1 = 2와 a_k = 1을 동시에 만족할 수 없기 때문입니다. 그러나 N=1일 때 자명한 해인 {1}이 존재하고, 구성한 수열의 패턴과 동일하므로, 문제가 되지 않습니다.
3) N을 3으로 나눈 나머지가 2라면, a_1은 3, 2 <= i <= k-2인 모든 i에 대하여 a_i를 2, 그리고 마지막 두 원소인 a_{k-1}과 a_k는 1로 정하면 됩니다.
앞선 경우와 마찬가지로 식을 세워보면 다음과 같습니다.
N = f(a_1) + f(a_2) + f(a_3) + ... + f(a_k)
= (a_1 + 3) + (a_2 + 1) + (a_3 + 1) + ... + (a_{k-2} + 1) + a_{k-1} + a_k
= a_1 + a_2 + a_3 + ... + a_k + k
>= a_1 + a_2 + a_3 + ... + a_k + (k-1)
따라서 {N N N 1 N N 1 N N 1 N N 1 ... N N 1 N 1 N 1}과 같은 수열을 구성하면 됩니다 (N N N 1로 시작, 이후 N N 1을 floor(N/3)-2번 반복, 마지막 부분은 N 1 N 1).
위와 같은 구성을 할 수 없는 경우는 N=2와 N=5입니다. f(a_1) = 6이므로, N을 초과하기 때문입니다.
이와 같은 경우는, 수열의 길이가 작기 때문에, 모든 경우를 전부 탐색해볼 수 있습니다. 실제로 브루트포싱을 이용하여 가능한 수열을 탐색해보면, N=2 또는 N=5일 때 조건을 만족시키는 수열이 단 한개도 존재하지 않음을 알 수 있습니다. 따라서 예외 케이스인 N=2, N=5를 먼저 처리해주고, 이외 경우들은 위와 같은 방법으로 수열을 구성하면 됩니다.
N을 3가지 경우로 나누어, N=2와 N=5를 제외한 모든 N에 대하여 조건을 만족시키는 수열이 존재함을 보였습니다.
2시간을 투자해도 보이지 않던 방법이 운동하고 오니까 30분만에 보이는군요... 이런 거 잘하려면 운동은 필수인가 봅니다.새로운 구성 방안을 생각해낸 것과는 별개로, 에디토리얼에서 설명한 방법의 정당성은 아직도 증명을 못하겠습니다. 아시는 분 있으면 좀 알려주세요...