백준 1193_분수찾기 파이썬

하아; 브론즈면 뭐하나...

 

 

⬇돌리지 않아도 시간초과 나는 코드

X = int(input())

count, index = 0, 1  # X번째까지, 숫자 차례대로
odd, find = True, False

while not find:
    if odd:
        numerator = index
        denominator = 1
    else:
        numerator = 1
        denominator = index
    for idx in range(index):
        if odd:
            numerator -= 1
            denominator += 1
        else:
            numerator += 1
            denominator -= 1
        count += 1
        if count == X:
            # print(f"{numerator}/{denominator}")
            find = True
            break
    index += 1
    odd = not odd

 

질문 검색에 '군수열'이라는게 있다는걸 알았고, 군수열이 뭔지 몰라서 자신 없어져서 그냥 빨리 답이나 봐야겠다는 생각이 들었다. 그러다가 친절하게 설명해준 분의 블로그를 찾았다.

https://aerimforest.tistory.com/94

[1193] 분수찾기

 

X = int(input())

index = 1  # 군수열 - 1군, 2군, 3군...

while True:
    now_group_first_idx = 1 + index * (index - 1) // 2  # 현재 군의 첫 번째 index
    next_group_first_idx = 1 + index * (index + 1) // 2   # 다음 군의 첫 번째 index
    if now_group_first_idx <= X < next_group_first_idx:  # 지금 숫자가 속한 군을 찾아내고
        if index % 2:  # 홀수 군이라면 분자 감소, 분모 증가
            numerator = next_group_first_idx - X  # 다음 군 첫 번째 index - 현재 군 첫 번째 index = 개수차이
            denominator = 1 + X - now_group_first_idx  # 원하는 index - 현재 군 첫 번째 index + 1
        else:
            numerator = 1 + X - now_group_first_idx  # 홀수일 때와 반대
            denominator = next_group_first_idx - X
        print(f"{numerator}/{denominator}")
        break
    index += 1

내가 만든 계산식이 아니라 그런지 이해하는데 오래 걸렸다.