[파이썬][백준 1193번] 분수찾기
1. 문제
[Bronze I] 분수찾기 - 1193
성능 요약
메모리: 30864 KB, 시간: 72 ms
분류
구현(implementation), 수학(math)
문제 설명
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
| 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)가 주어진다.
출력
첫째 줄에 분수를 출력한다.
출처: 백준, https://https://www.acmicpc.net/
2. 해결방법 시간복잡도
- 단순 코딩 O(N)
3. 문제 해결 및 코드
-
주석을 참고하면서 이해를 돕습니다.
4. 알고리즘 및 해설
- while문을 통해 해당 수에서 계속해서 돌아간 수만큼 빼준다.
- num값을 1부터 시작해서 계속해주고, 이때 N이 num이 되는 순간 멈추게 된다.
- 반복문이 끝난 이후 해당 돌아간 횟수가 짝수일 경우
- N값과 돌아간 횟수에서 N값을 빼고 1을 더한 값을 출력한다.
- 반복문이 끝난 이후 해당 돌아간 횟수가 홀수일 경우
- 돌아간 횟수에서 N값을 빼고 1을 더한 값과 N값을 출력한다.