https://www.acmicpc.net/problem/14723
시간 1초, 메모리 256MB

input :

• N(1 ≤ N ≤ 1,000)

output :

• 분자 a, 분모 b를 공백으로 구분하여 a, b를 출력

---

너무 오래 걸려서 확인했다.

다음 풀이

1. 입력값의 범위
2. 규칙? 완전 탐색

일단 입력값의 범위가 매우 작다.
그냥 다 만드는 경우의 수도 생각해야 한다.
이 문제에서는 직접 카운팅 하는 것도 가능하다. 합이 2인 유리수 1개, 3인 유리수 2개, 4인 유리수 3개 ... 로 증가한다.

그렇기 때문에 cnt, prev를 두고 해당하는 개수를 체킹한다.
그 이후에 prev - n만큼 1에다가 더해서 분자를 구하고, 그와 반대로 분모를 구할 수 있다.

신기하게도 분자의 시작값이 합과 동일한 것도 알 수 있다.

import sys

n = int(sys.stdin.readline())
cnt, prev = 0, 0

for i in range(1, 1000):
    prev = cnt
    cnt += i
    if cnt >= n:
        break

up, down = i, 1
for i in range(n - prev - 1):
    up -= 1
    down += 1

print(up, down)