[백준] 1193번 분수찾기 | 파이썬 Python

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

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

 

입력

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

 

출력

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

 

예제

 

나의 풀이

n = int(input())
a = 1   
b = 1
down = True

for _ in range(n-1):
    if a == 1 and b%2 == 1:
        b += 1
        down = True
    elif a%2 == 0 and b == 1:
        a += 1
        down = False
    elif down:
        a += 1
        b -= 1
    elif not down:
        a -= 1
        b += 1

print(f"{a}/{b}")

• 지그재그 이동 규칙을 네 가지 경우로 나눴다.
• 답은 나오는데 시간 초과에 걸려서 실패했다.

 

다른 사람의 풀이

n = int(input())
line = 1

while n > line:
    n -= line
    line += 1

if line%2 == 0:
    print(f"{n}/{line-n+1}")
else:
    print(f"{line-n+1}/{n}")

• 배열을 대각선으로 나눠보면 한 줄에 n개의 요소가 포함된다. `n-line`을 반복해서 입력값이 몇 번째 줄에 위치하는지를 구한다.
• `line`이 짝수인 경우에는 밑으로 내려가면서 값이 커지고, 홀수인 경우에는 위로 올라가면서 값이 작아지는 점을 이용해서 각각 다른 방법으로 계산한다.
• `line`의 `n`번째에 위치하는 값을 조정해서 출력한다.

 

참고

• [백준 1193 파이썬] - 분수찾기