[BOJ/백준] 분수 찾기

문제

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

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)가 주어진다.

---

출력

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

결과

---

코드

n = int(input())
stage , key = 1,1
#key에 stage를 누적하면서 n이 어떤 스테이지에 있는지 찾는다
while key+stage <= n :
  key += stage
  stage += 1

#stage는 행과 같으므로 열과 같은 동작을 할 step 선언

step = n - key
x,y = step + 1 ,stage - step

if stage % 2 == 0 :
  print('{}/{}'.format(x,y))
if stage % 2 == 1:
  print('{}/{}'.format(y,x))

결과

---

코드 풀이

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
...	...	...	...

예제에 적힌  1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 구조를 표로 나열해보면 이렇게 나타낼 수 있다.

입력 값에 따라 stage + 1 = 분모 + 분자를 만족하는 stage로 구분할 수 있고 stage안에 소속되어 있는 X의 개수 또한 같다.

또한 stage가 짝수냐 홀수냐에 따라서 규칙이 나누어진다.

 

stage가 짝수라면 분자는 상승하고 분모는 감소한다.

stage가 홀수라면 분자는 감소하고 분모는 상승한다.

 

이런 규칙 따라서 코드를 작성하면 된다.

 

1. stage를 구분할 stage, key를 1로 초기화한다.
2. key에 stage를 누적하면서 입력 값이 어떤 스테이지에 있는지 확인한다.
3. step이라는 변수를 열과 같이 동작하도록 선언한다.
4. 입력값이 홀수냐 짝수냐에 따라서 출력한다.