<1193>
문제:
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
|
1/1
|
1/2
|
1/3
|
1/4
|
1/5
|
…
|
|
2/1
|
2/2
|
2/3
|
2/4
|
…
|
…
|
|
3/1
|
3/2
|
3/3
|
…
|
…
|
…
|
|
4/1
|
4/2
|
…
|
…
|
…
|
…
|
|
5/1
|
…
|
…
|
…
|
…
|
…
|
|
…
|
…
|
…
|
…
|
…
|
…
|
이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
첫번째 줄에 X(1 ≤ X ≤ 10,000,000)를 입력하고 분수를 출력하자.
나는 규칙을 위와 같은 피라미드 형식으로 생각하였다.
첫번째 줄에서는 분모와 분자의 합이 2, 두번째 줄에서는 분자의 합이 3, 세번째 줄에서는 분자의 합이 4... 이런식으로 한줄 씩 내려갈 수록 분자와 분모의 총합이 증가하고 같은 줄에서는 분자와 분모의 합이 일정하다.
정수 K는 그 줄 까지의 번호를 나타낸다. 즉 그 줄의 마지막 번호이다.
한 줄씩 내려갈 때마다 T값이 더해지는데, T는 2부터 시작하여 줄이 바뀔 때마다 1씩 증가한다.
따라서 K는 그림에서 나타낸 것과 같이 1,3,6,10,15,21.. 순으로 증가한다.
T가 짝수일 때, 그 줄은 분모가 1부터 시작하여 1씩 증가하고 , T가 홀수일 때는 그 줄의 분자가 1부터 시작하여 1씩 증가한다.
간단하게 생각하면 T는 '줄이 바뀔 때마다 K에 더해지는 값'이라고 생각하면 될 것 같다.
분수의 분모를 a , 분자를 b라고 설정하였다.
분자가 1에서 시작할 때, 분수의 분모는 그 줄에 해당하는 수의 합에서 이전 줄의 K값을 빼고, T를 더한 뒤,
1을 뺀 값이다.
즉 , X-(K-(T-1)) 인데, 간단하게 X-K-T-1 로 나타내었다.
T가 홀수일 때는 분자와 분모를 바꿔주기만 하면 된다.
풀이:
X = int(input())
K = 1
T = 2
while(True):
if X <= K: #몇번 째 줄에 있는지 확인
if T % 2 == 0: #T가 짝수일 때 = 분자가 1로 시작할 때
a = X - K + T - 1
b = T - a
print(b, "/", a,sep="")
break
else: #분모가 1로 시작할 때
b = X - K + T - 1
a = T - b
print(b,"/",a,sep="")
break
else: #해당 줄에 없다면 K에 T더하고 T값 증가
K += T
T += 1
입력:
14출력:
2/4