[1193] 백준 문제풀이 - 분수찾기

https://www.acmicpc.net/problem/1193

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

풀이

1 - 오답(메모리 초과) 처음에는 직접 그 수의 범위에 맞는 배열을 직접 만들어서 인덱스로 풀이할려고했으나 수가 일정이상 늘어나면 메모리 초과로 오답이 나왔다.

2 - 정답 $1/1 – 1/2, 2/1 – 3/1, 2/2, 1/3 – 1/4, 2/3, 3/2, 4/1$ 규칙이 보이는가? $1/N$이 있을 때 $N$에 해당하는 대각선의 갯수는 총 $N$개 이다. 즉 $N$이 증가할 때마다 $1+2+3+4+5+…$식의 팩토리얼 구조를 띄고있다. 내가 한 풀이는 이런식으로 팩토리얼의 합이 $X$를 넘었을 때 그 $X$에 해당하는 배열을 만들고 그 배열의 인덱스를 구해주어 풀이했다.

N = int(input())

count = 0
temp = 0
while temp < N:
    count += 1
    temp += count

temp -= N
# 홀수일때는 올라가고 짝수일때는 내려가고

arr = []
for i in range(count, 0, -1):
    arr.append((i, count - i + 1))

if count % 2 == 0:
    print(f"{arr[temp][0]}/{arr[temp][1]}")
else:
    print(f"{arr[len(arr) - (temp + 1)][0]}/{arr[len(arr)-(temp+1)][1]}")