[백준] 1193 : 분수 찾기 (Python/파이썬)

문제 링크

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

출력

1/1

입력

5

출력

2/2

---

정답 및 풀이

규칙

1. 대각선 그룹
   • 1번째 대각선: 1/1 (1개)
   • 2번째 대각선: 1/2, 2/1 (2개)
   • 3번째 대각선: 3/1, 2/2, 1/3 (3개)
   • 4번째 대각선: 1/4, 2/3, 3/2, 4/1 (4개)
2. n 이 홀수냐 짝수냐에 따라 분수의 숫자가 달라짐
   • 홀수 대각선: 분자가 큰 것부터 시작 (ex. 3/1 → 2/2 → 1/3)
   • 짝수 대각선: 분모가 큰 것부터 시작 (ex. 1/4 → 2/3 → 3/2 → 4/1)

코드

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}")

1. n = int(input())
   • 몇 번째 분수를 찾을지 입력
2. line = 1
   • 현재 대각선 번호
3. while n > line :
   • n 이 현재 대각선 크기보다 크면
4. n -= line
   • n 에서 현재 대각선에 있는 분수 개수를 빼줌
5. line += 1
   • 다음 대각선으로 이동
6. if line % 2 == 0:
   • 대각선 번호가 짝수일 때
   • 분모는 커지고, 분자는 작아짐

---