[BOF/Python] 1193번, 분수찾기

📜 문제

BOF 1193번, 분수찾기

🔥난이도🔥

1차 풀이 ⭕

---

분수를 지그재그 순서로 나열했을 때 입력된 X 번째의 분수를 구하는 문제다.

대각선 진행 방향(↗︎↙︎)의 끝이 계차수열로 증가하는 규칙을 통해 문제를 풀 수 있다.

표에서 대각선 진행 방향의 마지막 순서를 보면 1 -> 3 -> 6 -> 10 -> 15 순으로 계차수열로 증가하는 것을 알 수 있다.

문제의 풀이 순서는 아래와 같다.

1. 입력값이 대각선 진행 방향의 마지막 순서보다 작거나 같은 때까지 반복한다.

2. 반복될 때마다 계차수열을 1 증가시킨 후 an에 더해 다음 대각선 진행 방향의 마지막 순서를 구한다.

3. 위 과정을 반복하여 입력된 값이 어느 대각선 라인에 존재하는지 구할 수 있다.

4. an(대각선 마지막 순서)에서 입력값을 뺀다.

5. 대각선의 순서에 따라 분자와 분모의 값을 계산한다.

   • 홀수(↗︎) : 분자 = 1 + sub, 분모 = n - sub

   • 짝수(↙︎) : 분자 = n - sub, 분모 = 1 + sub

• while 문이 반복될 때마다 an이 1 -> 3 -> 6 -> 10 -> 15 -> … 으로 증가한다.
• 계차수열의 값이 대각선 라인에서 가장 큰 분모 값이다.

코드

X = int(input())

an = 1    # 수열 an
b = 1     # 증가 값

# 입력값이 수열 an보다 작거나 같을 때까지 반복
while X > an:
    b += 1     # 계차수열(+1)
    an += b    # 계차수열만큼 증가

sub = an - X   # 수열 an - 입력값

# b가 홀수(↗︎)
if b % 2 == 1:
    # 분모 : 
    print(f'{1 + sub}/{b - sub}')
# b가 짝수(↙︎)
else:
    print(f'{b - sub}/{1 + sub}')

결과

보충 🤓

---

계차수열이란?🤔

위키백과 계차수열

현재 티어 🥈

---