[#48][알고리즘] 분수찾기
백준 > 분수찾기
문제 링크(https://www.acmicpc.net/problem/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)가 주어진다.
출력
첫째 줄에 분수를 출력한다.
예제 입력 1
14
예제 출력 1
2/4
#include <iostream>
using namespace std;
int main() {
int number, t1, t2, i;
cin >> number;
for (i = 1;; i++) {
if (number -i <= 0) {
i % 2 == 1 ? t1 = i - number + 1 : t1 = number;
i % 2 == 1 ? t2 = number : t2 = i - number + 1;
break;
}
number -= i;
}
cout << t1 << "/" << t2 << endl;
return 0;
}
| cs |
t2의 최대값을 구하는 과정
i = 1 부터 i++
i=1 : 9 - 1 > 0
i=2 : 8 - 2 > 0
i=3 : 6 - 3 > 0
i=4 : 3 - 4 <= 0
number = 3, i = 4 => t2는 최대 4이다.
t2가 짝수/홀수에 따라 시작 순서가 달라짐
(t2가 짝수)
t1 = number = 3
t2 = i - number + 1 = 4 - 3 + 1 = 2
-------------------------------------------------------------------------------------------------
입력 = 4일 때
t2의 최대값 구하는 과정
i = 1 부터 i++
i = 1 : 4 - 1 > 0
i = 2 : 3 - 2 > 0
i = 3 : 1 - 3 <= 0
number = 1, i = 3 => t2는 최대 3이다.
(t2가 홀수)
t1 = i - number + 1 = 4
t2 = number = 1
댓글
댓글 쓰기