Problem
https://www.acmicpc.net/problem/1193
Solution
오답코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
x = int(sys.stdin.readline())
k, v, count = 1, 1, 1
while count < x:
if k == 1: # 제일 윗 행일 때
if v % 2 == 1: # 분모가 홀수
v += 1
count += 1
else: # 분모가 짝수
while count < x and v > 1:
k += 1
v -= 1
count += 1
elif v == 1: # 제일 왼쪽 열일 때
if k % 2 == 0: # 분자가 짝수
k += 1
count += 1
else: # 분자가 홀수
while count < x and k > 1:
k -= 1
v += 1
count += 1
print(k, v, sep='/')
위 코드는 시간초과로 오답처리가 된 코드이다. 문제를 제대로 이해하지 못하고 주어진 순서에 해당하는 분수를 찾는 과정을 매우 비효율적으로 설계하였기 때문이라고 생각한다.
정답코드
1
2
3
4
5
6
7
8
9
10
x = int(input())
n = (2*x + 1/4)**(1/2) - 1/2
n = int(n) if n % 1 == 0 else int(n) + 1 # 해당 대각선줄의 번호(올림 후 정수로)
line_order = int(x - n*(n-1)/2 - 1) # 해당 대각선줄에서의 인덱스(0부터 시작)
if n % 2: # n이 홀수인 경우
print(n-line_order, 1+line_order, sep='/')
else: # n이 짝수인 경우
print(1+line_order, n-line_order, sep='/')
undefined 위의 표를 보면 분자는 row를, 분모는 column을 각각 나타낸다는 것을 알 수 있다. 하지만 이것을 풀이에 적용시키기에는 무리가 있었다. 대신 이 표에서 다른 규칙성을 찾을 수 있는데, 하나의 이동경로인 대각선 상에 있는 값들은 분자와 분모의 합이 동일하다. undefined 이렇게 값을 대각선으로 분류하여 안의 값들을 내림차순(분모는 오름차순)으로 정리하면 1번 대각선은 1/1, 2번 대각선은 (2/1, 1/2), 3번 대각선은 (3/1, 2/2, 1/3), 4번 대각선은 (4/1, 3/2, 2/3, 1/4), 5번 대각선은 (5/1, 4/2, 3/3, 2/4, 1/5), ··· 와 같이 나오게 된다.
※ 풀이 포인트
- 각 라인에 속하는 값의 개수는 1, 2, 3, 4, 5, 6, ··· 으로 1씩 증가하는 형태를 보인다. 따라서 n번 라인까지의 누적된 칸의 개수(==n번 라인의 끝값의 순번)는
1 + 2 + 3 + ··· + n이 된다. - 각 라인의 첫값의 분자가 홀수, 짝수냐에 따라 이동방향이 순방향, 역방향으로 달라진다.
여기까지 정리가 되면 다음으로는 입력된 정수(==순번)가 몇번째 라인에 속하는지 판단하는 것인데, 이 과정에서는 고등학교때 배웠던 정수의 합 공식을 활용하였다. n(n+1)/2 = x라는 식을 정리하여 n = (2*x + 1/4)**(1/2) - 1/2와 같은 계산식을 얻어냈다. 값을 올림한 이유는 x가 6일때는 n이 3으로 제대로 나오지만 5인 경우 3번째 줄에 속해있지만 n값은 2.7016으로 나오기 때문이다. 다음은 해당 대각선에서 몇번째 인덱스의 값인지를 구했는데 이는 (해당 칸까지의 누적값) - ((n-1)번째 줄까지의 누적값) - 1과 같이 구할 수 있다.
Memo
이번 문제는 문제의 원리에 대해 얼마나 자세히 파악하고 있는지에 따라 그 풀이과정의 효율성이 극명하게 갈리는 것 같다.