[Baekjoon/Python] 백준 1193 : 분수찾기

[Baekjoon/Python] 백준 온라인 저지 1193번 : 분수찾기

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

 

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

 

 

출력 ::

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

 

 

예제 입력 ::

14

 

 

예제 출력 ::

2/4

 

 

정답 코드 ::

 

n = int(input())
line = 1

while n > line:
  n -= line
  line += 1

if line % 2 == 0:
  dx = n
  dy = line - n + 1
  print(f"{dx}/{dy}")

else:
  dx = line - n + 1
  dy = n
  print(f"{dx}/{dy}")

 

 

사선으로 이동한다.

노트에 1부터 14까지 값을 적어보았다.

 

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

10 :: 4/1

11 :: 5/1

12 :: 4/2

13 :: 3/3

14 :: 2/4

 

여기서 알 수 있는 규칙이 있다.

count	n	분수	분자 + 분모
1	1	1/1	2
2	2, 3	1/2, 2/1	3
3	4, 5, 6	3/1, 2/2, 1/3	4
...	...	...	...

 

• 1의 경우 한 칸 2의 경우 값이 두개, 3의 경우 값이 3개씩 묶인다.
• count 값이 짝수 일때 분자는 1부터 증가, 분모는 count 값부터 감소
• count 값이 홀수 일때 분자는 count 값부터 감소, 분모는 1부터 증가
  
  
• while문의 경우 x번째 분수가 있는 위치를 알기 위한 코드이다.
  n = 14, 13, 11, 8, 4
  line = 1, 2, 3, 4, 5
  n = 4, line = 5인 위치가 14번째 분수가 있는 위치이다.
  
  
• 짝수와 홀수의 코드는 n = 4와 line = 5라는 것으로 분자, 분모 코드를 맞춰서 짜주면 끝.