백준 알고리즘 1193 (분수찾기) - python

[ 문제 ] 백준 알고리즘 1193 - python (분수찾기)

> https://www.acmicpc.net/problem/1193

1193번: 분수찾기

 

1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> ... 를 구조적으로 다시 정리하면, 아래 표와 같이 된다. 

stage	X	분수	분모+분자
1	1	1/1	2
2	2, 3	1/2, 2/1	3
3	4, 5, 6	3/1, 2/2, 1/3	4
4	7, 8, 9, 10	1/4, 2/3, 3/2, 4/1	5
...	...	...	...

 

 

입력 X에 따라 생기는 분수의 특징을 보면, 분모 + 분자 = stage+1을 만족하는 stage로 구분 가능하고,

 

stage와 그 안에 소속되는 X의 개수는 같은 특징을 지닌다.

 

그리고, stage의 값이 홀수 / 짝수일 때의 규칙이 다르다.

 

1. stage 값이 홀수일 때 : 분자는 1부터 증가, 분모는 stage 값부터 감소

 

2. stage 값이 짝수일 때 : 분자는 stage 값부터 감소, 분모는 stage 1부터 증가

 

 

이를 코딩으로 적용하기 위해서 몇 가지 방법을 적용했다.

 

각 stage의 첫 번째 X는 key_X라고 명명할 것인데, 이를 이용해서 stage를 구분 짓는데에 사용할 것이다.

 

key_X에 stage 값을 누적하면서, X가 어떤 stage에 있는지 검사한다.

 

stage는 행과 같이 동작하므로, 열과 같이 동작하는 step이라는 변수를 만들어 사용할 것이다.

 

[Code]

X = int(input())
stage, key_X = 1, 1
while key_X + stage <= X:
    key_X += stage
    stage += 1
step = X - key_X
x, y = step + 1, stage - step
if stage % 2 == 0:
    print('{}/{}'.format(x, y))
else:
    print('{}/{}'.format(y, x))