Programming/백준 문제풀이

[백준] 1193번 분수 찾기 C/C++ 풀이

bjloed 2020. 4. 21. 17:38

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

 

1193번: 분수찾기

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

www.acmicpc.net

 

풀이

먼저 모든 양의 유리수의 집합은 셀 수 있는 무한집합이다.

양의 유리수의 수열은 다음과 같이 나타낼 수 있다.

r1,r2,...,rn

또한, 다음 유리수들은 n/d의 형식으로 되어있고 다음과 같은 규칙을 찾을 수 있다.

n+d=2,n+d=3,n+d=4...n+d=cnt

첫번째 for문에는 cnt의 값을 찾는 코드를 작성한다.

두번째 for문에서는 cntmod2 의 값에 따른 분자와 분모의 값을 구하는 코드를 작성한다.

 

C/C++ 풀이