분수를 배치한 2차원 배열에 1부터 인덱스를 부여하여 인덱스 N은 어느 분수를 가리키는지 찾는 문제입니다. 이 문제는 분수의 분모와 분자 둘 다 찾아야 하므로 식이 2개 필요합니다.
먼저 분자입니다. 분자는 [1, 1, 2, 3, 2, 1, 1, 2, 3, 4, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, ...]와 같이 됩니다. 수가 증가하고 감소하는 부분을 기준으로 잘라보면 [1], [1, 2, 3, 2, 1], [1, 2, 3, 4, 5, 4, 3, 2, 1], …와 같이 됩니다. 각각의 길이는 1, 5, 9로 4n-3 꼴임을 알 수 있습니다. 이제 각 블럭의 숫자의 의미를 생각해봅시다. 각 숫자는 다음 블럭의 첫 번째 원소까지의 거리와 이전 블럭의 마지막 원소까지의 거리 중 작은 것이라고 볼 수도 있겠습니다. 아무 블럭이나 하나 잡아서 보면 그럴듯하다는 것을 알 수 있습니다.
이제 인덱스가 주어졌을 때 몇 번쨰 블럭에 있는지 알아내는 식을 만들어봅시다.
\[S_n=\sum_{i=1}^{n}4i-3=4\times\sum_{i=1}^{n}i-3n=2n^2+2n-3n=2n^2-n\\ 8S_n=16n^2-8n\\ 8S_n+1=16n^2-8n+1=(4n-1)^2\\ \sqrt{8S_n+1}=4n-1\\ n=\frac{\sqrt{8S_n+1}+1}{4}\]이제 \(S_n\) 자리에 몇몇 인덱스를 넣어보면 다양한 값이 나옵니다. 예를 들어 인덱스 5를 넣어보면 \(n=\frac{\sqrt{41}+1}{4}\)로 1.85…의 값이 나옵니다. 그런데 인덱스 5는 2번쨰 블럭에 포함되어있으므로 올림 연산을 이용하면 어느 블럭에 있는지 알 수 있습니다. 이렇게 나온 값을 블럭 번호를 \(a\)라고 하면 이제 이 인덱스의 숫자는 \(a\)의 값을 이용하여 구할 수 있습니다. 위에서 이전 블럭의 마지막 숫자와의 거리와 다음 블럭의 첫 숫자와의 거리를 구한다고 했으므로 각각 구해봅시다. 먼저 이전 블럭의 마지막 숫자는 \(a-1\)개의 블럭의 길이를 모두 더한 것과 같을 것입니다. 따라서 위에서 구한 식을 이용하면 \(2(a-1)^2
다른 풀이(a-1)=2a^2-5a+3\)으로 쉽게 구할 수 있습니다. 다음 블럭의 첫 숫자는 (현재 블럭의 마지막 숫자의 위치+1)에 위치할 것이므로 \(2a^2-a+1\)이 됩니다. 찾으려는 인덱스를 x라 하면 x에 위치할 숫자는 \(\min(2a^2-a+1-x,x다른 풀이(2a^2-5a+3))\)이 될 것입니다. 이 식으로 분자를 구할 수 있습니다.
분모도 분자와 같은 방법으로 구할 수 있습니다. 분모의 경우는 4n-3이 아닌 4n-1 길이의 블럭들이 위치하며, 숫자의 의미는 같습니다. 찾으려는 블럭 번호를 \(b\), 찾으려는 숫자를 \(y\)라고 하여 수식을 나타내보면
\[S_n=\sum_{i=1}^{n}4i-1=4\times\sum_{i=1}^{n}=2n^2+n\\ n=\frac{\sqrt{8S_n+1}-1}{4}\\ b=\lceil n\rceil\\ \text{previous block loc.}=2(b-1)^2+(b-1)=2b^2-b+1\\ \text{next block loc.}=2b^2+b+1\\ y=\min(2b^2+b+1-y,y다른 풀이(2b^2-b+1))\]
이 됩니다. 이를 코드로 구현하면 문제를 풀 수 있습니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-25 21:10:56 |