백준 알고리즘 1193번(파이썬)

 

백준 1193번_파이썬 알고리즘

Q. 백준 1193. 분수찾기

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

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

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

(2) 출력 : 첫째 줄에 분수를 출력한다.

 

입력 예시	출력 예시
1	1/1
2	1/2
3	2/1
4	3/1
5	2/2
6	1/3
7	1/4
8	2/3
9	3/2
14	2/4

---

A. 풀이

# Q 백준 1193. 분수 찾기 ★★
# 분수 : 1/1 1/2 2/1 3/1 2/2 1/3 1/4 2/3 3/2 4/1 5/1 4/2 3/3 2/4 1/5 ...
# 분자 : 1 / 1 2 / 3 2 1 / 1 2 3 4 / 5 4 3 2 1 / 1 2 3 4 5 6 /
# 분모 : 1 / 2 1 / 1 2 3 / 4 3 2 1 / 1 2 3 4 5 / 6 5 4 3 2 1 / 
# 순서 : 0   1 0   2 1 0 
# 그룹 : 1    2      3        4          5            6
# 순번 : 1     3       6         10          15

N = int(input())        # N번째 수 입력

num = 0     # 분자
den = 0     # 분모

cnt = 0     # 순번
grp = 0     # 그룹

nx  = 0     # 홀, 짝


while N > cnt:
    # N -= cnt
    grp += 1
    cnt += grp
    
    # print(f"그룹 : {grp}")
    # print(f"그룹 마지막 순번 : {cnt}")
    # print("-------------")
    
if grp % 2 == 0:      # 짝수 그룹
    nx = 0
    num = grp-(cnt-N)
    den = cnt-N+1
else:                 # 홀수 그룹
    nx = 1
    num = cnt-N+1
    den = grp-(cnt-N)

# print(f"그룹 : {grp}")
# print(f"그룹 내 {grp - (cnt-N)}번째")
print(f"{num}/{den}")